Why don't you keep a pre-sorted index array of all the hash keys along with your hash. This would only have to be regenerated when you add or remove hash elements.

Then, you can use a binary search to look up your hash key in the index array and return the next largest key.

This eliminates the sort involved with each lookup, which I would guess is the biggest slowdown to your current code.

It also changes your search from simple to binary, which should cut the search time by an order of magnitude.