How to fix the entropy pool issue with RHEL 5.x
Solution 1:
As has been pointed out, colocated servers, lacking that random human being to create entropy, generally don't have much of it to spare. If you have a physical server with a spare USB port, and a demonstrable need for high-grade entropy, you could do worse than get yourself an Entropy Key. I don't normally recommend specific products on SF, but I rather like this one, and it does the job nicely.
Here's the depth of my pool before fitting the key:
and here's the pool after:
Declaration of interest: I have no connection with the makers except that I bought one of their products, at full price, and like it.
Edit (July 2015): the Entropy Key website has for some time said that they're out of stock, and they don't know when they'll have more made. However, OneRNG, a project to make a completely-open, verifiable, USB-connected entropy generator, was fully funded on kickstarter, and at the time of writing intends to start selling them via a webstore once their kickstarter obligations are fulfilled.
Solution 2:
I don't know how much entropy you need, but you could use the HTTP API on random.org to feed entropy into your system (try rand_add). Or you could use something like the Entropy Gathering Daemon.
Solution 3:
Change the t parameter to .1 or .001