Thankfully, there is a solution, and it's thankfully a very simple one. Haveged is a simple entropy demon that generates random data based on processor flutter. It requires very little resources to run, and will "fill up" the random number pool when it reaches 1024, which is more than ample for all but extremely heavy systems.
On CentOS 6 and CentOS 7 systems, we can install haveged and ensure it runs after reboot by running the following commands in SSH:
sudo yum install epel-release -y
sudo yum install haveged -y
sudo service haveged restart
sudo chkconfig haveged on
After haveged is installed, we can immediately see the level of entropy available is consistently higher on cloud servers than previously. Rarely will we see the level of entropy drop below 1000. We can check the level of entropy available with the following command:
cat /proc/sys/kernel/random/entropy_avail