Identical Droplets in the DigitalOcean: Regenerate your Ubuntu SSH Host Keys now
SSH host keys are problematic on cloud servers, not just because of this problem, but also because if the cloud provider does the right thing and generates the SSH host key on the first boot, the key is generated when the system has very little entropy available.  The primary sources of entropy on Linux are key/mouse input, disk latency, and network interrupts.  There's obviously no keyboard/mouse on a server, and in an SSD environment like DigitalOcean, disk latency is quite uniform and thus useless as a source of entropy.<p>Linux distros mitigate the cold boot entropy problem by saving some state from the RNG on shutdown (on Debian, it's saved in /var/lib/urandom/random-seed) and using it to seed the RNG on the next boot.  On physical servers this obviously isn't available on the first boot, and on cloud servers, the provider often bakes the same random-seed file into all their images, so everyone gets the same seed on first boot (fortunately this doesn't harm security any more than having no random-seed file at all, but it doesn't help either).  What cloud providers should really do is generate (from a good source of randomness) a distinct random-seed file for every server that's created, but I haven't seen any providers do this.