The host key and the SSH key you use to log in are two different things.
One authenticates the host for you to verify (the host key), and the other one is the key you use to identify yourself and authenticate to your account.
If you delete a droplet and create a new one with the same IP, for instance, you will see a SSH host key verification failed because the SSH host key of your first droplet and the second one aren't the same. This is a security feature so you can detect man in the middle attacks.
When you restore a snapshot, unfortunately DigitalOcean messes around a lot of files, especially the SSH ones. Even if you carefully prepare your host key, note down its fingerprint and then snapshot hoping to restore it as-is, you'll find that they heavily modify your disk image upon restoration, leading to these sort of errors.
The only "safe" way to prevent MitM attacks on your box is this:
Take a snapshot, restore it, reset the root password, log in through web console, check the SSH host key fingerprint, then log in over SSH verifying the key.
If you don't want to risk filesystem corruption when resetting the root password, restore your droplet using a password rather than the SSH keys. You will be asked to change it on first log in.