The order is not random in a cryptographic sense. It simply has no bearing on the order in which elements were added and no apparent bearing on the keys. The order in which keys, values and each return their results is based on the internal format of the hash.

The internal format of the hash does not change if no keys are added to the hash, so the order is guaranteed not change if no change is made to the hash. @hash1{keys %hash2} = values %hash2; will work, for example.

In fact, if you repeat the steps you used to create a hash to create a new hash in the same process, the new hash should be in the same order.

Anyway, the point is that "random" is not a goal, but a possible side-effect.

Unrelated, a security measure has been in place since Perl 5.8.1 to randomize the order between perl processes. That means if repeat the steps you used to create a hash to create a new hash in the different process, the new hash may be in a different order.

So your test fails (by not returning failures) for two reasons:
An unchanged hash doesn't change its order.
You only have one process involved, so the security measure isn't applicable.