I did some more meditation and research...

First of all I have to say, that I can't possibly see why one would want to store a "representative key" of a hash in another structure (like the OP did)

Unless you want only to check if the hash is populated, then

  DB<129> scalar %empty
 => 0
[download]

will do the trick without side effects ( scalar keys %empty would reset the iterator).

Also the usual trick to copy a hash before iterating (in order to protect the iterator) is far slower than assigning to a one element list (which can't compete with each)

  DB<100> $h{$_}=$_ for 1..5e6

  DB<101> $t=time; %h2=%h; print time-$t;
124
  DB<102> $t=time; ($k)=%h; print time-$t;
19
  DB<103> use Time::HiRes qw(time)

  DB<104> $t=time; ($k)=each %h; print time-$t;
7.70092010498047e-05
[download]

BUT I have to say I'm very critical about hashes of that size, because memory consumption can easily freeze your system.¹

Depending on use case I'd either consider using a database or a hash of hashes (of hashes ...) which is far more "swap friendly".

¹) even emptying a hash with 5e6 entries can take minutes on a netbook.