My question to you is:
What significance do you place on a particular ordering of the hash keys?
As others have stated, there is no particular logic to the sequence that keys(%hash) will return. And while that will remain constant while ever you make no changes to the contents of the hash itself, I certainly don't believe you can rely on them being in "arrival order".
Maybe what you need to determine first is why you need the values returned in a particular sequence, and you may find that a simple has (key / value) is not the data structure you require. Maybe a "hash of hashe", with the main key being some sequencing value (timestamp, transaction number, and so on), with the inner hash consisting of the values relating to that key.