Quoting chapter and verse from perldoc -f keys:

...
number of keys.)  The keys are returned in an
apparently random order.  The actual random order
is subject to change in future versions of perl,
but it is guaranteed to be the same order as
either the "values" or "each" function produces
(given that the hash has not been modified). ...
[download]

So I'd say the answer is probably yes. Of course you can always store off the list once and use a slice to extract the corresponding values in the same order whenever you need.