See if the rng-tools or haveged packages are available. Both of these harvest additional entropy, and are invaluable for solving the entropy starvation issues with Linux in any virtual machine environment.

If they're already installed and running, you might look for AWS-specific instructions for tuning to maximize harvested entropy.