People seem to be addressing the problem of speed via brute force. Why not just pregenerate them and queue them up? If you are getting millions of new session people in an hour, I'm sure you can get enough iron to pregenerate those.

A good function that goes through a range of numbers and doesn't repeat after some huge N, isn't hard. Using that as a seed to SHA-1, MD5 or even RC4 isn't killer. Queueing isn't hard. There you go. :) And if you are smart about your function, the next one is hard to guess, but THAT is a science all in itself and a harder one. Also making sure the encryption isn't easily analyzed from session key to session key is hard, but it is easy as well.