The ssh daemon uses host keys to uniquely identify itself to connecting clients. The host keys are typically stored in /etc/ssh. Security best practices dictate that these host keys be unique for each operating system instance. DigitalOcean typically removes host keys when creating a new Droplet from a snapshot or a standard image.
The SSH host keys for some Ubuntu-based systems could have been duplicated by DigitalOcean's snapshot and creation process. Therefore, our system is now configured to remove the host keys on Droplets that are created from snapshots at the time of the first boot. This removal process only happens in situations where we have a high degree of confidence that the host-keys will be regenerated on boot.
Most Linux distributions will generate new host keys at boot time if host keys are not found. However, some images may not do this due to local customization. This can be resolved in the majority of cases simply by logging in to the virtual terminal on the Droplet control panel, adding the following line to /etc/rc.local:
test -f /etc/ssh/ssh_host_dsa_key || dpkg-reconfigure openssh-server
and rebooting the affected Droplet.
DigitalOcean also recommends that users of existing Ubuntu-based Droplets and snapshots regenerate their SSH host keys. To do this, ensure that the above test or an equivalent is in place, remove the host keys, and generate new ones following the procedure below.
Step 1: remove potentially duplicated host key.
Step 2: regenerate host keys.
For snapshots, please create a Droplet from the snapshot, apply the above changes, and create a new snapshot from that Droplet. Then, after making sure your snapshot is functional by spinning up a new Droplet, you can delete the old snapshot and the new Droplet.
UPDATE: Sometimes using the dpkg-reconfigure script throws an error instead of generating new keys. Should this happen to you, please run the following commands to manually generate keys:
ssh-keygen -t dsa -N "" -f /etc/ssh/ssh*host*dsa*key
ssh-keygen -t rsa -N "" -f /etc/ssh/ssh*host*rsa*key
ssh-keygen -t ecdsa -N "" -f /etc/ssh/ssh*host*ecdsa_key