Why do you need a random key from the hash? How many do you need?

The order of hash keys is for all intents and purposes "random" (unordered, with a security randomization added in Perl 5.8.1 I think), so for some purposes you can just take the first n hash keys...

For some purposes, this is good enough.