Perl hashes have no guarantee of key ordering. See keys and Algorithmic Complexity Attacks. You might be able to randomize the order of the keys by changing the internal parameters used by Perl.

A better solution is to do something like @randomized_keys = List::Util::shuffle(keys %hash) and then accessing the corresponding values with something like @corresponding_values = @hash{@randomized_keys} (untested).