You could associate the insertion order with the hash key.

$hash{ $key }{order} = $InsertionOrder++;

Then you could continue to use $hash{ $key } as before. When you need the information in insertion order, you could search the hash for the desired  {order} value.