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.
No comments yet.