In my experience, 'haveged' [1] has worked out really well for generating entropy on headless servers. It could be scripted into a provider's base distribution

In my experience, 'haveged' [1] has worked out really well for generating entropy on headless servers. It could be scripted into a provider's base distribution to include the haveged binary and run haveged before generating the SSH host keys. [1] http://freecode.com/projects/haveged http://freecode.com/projects/haveged