Ok, here is the solution:

1. Enable the correct Kex:

sudo nano /etc/ssh/sshd_config

append with these lines to ensure correct digest:

KexAlgorithms diffie-hellman-group1-sha1,curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group14-sha1
Ciphers 3des-cbc,blowfish-cbc,aes128-cbc,aes128-ctr,aes256-ctr

Regenerate all keys:

ssh-keygen -A

Credit goes here

and then restart ssh service:

sudo service ssh restart

After these steps you would need to update your local known_hosts file, as the SSH key has changed.
Say, your Digital Ocean droplet IP is 255.255.222.211.

Locate it in ~.ssh/known_hosts and remove the line that begins with this 255.255.222.111.

In a new shell window test you can connect to your instance!

Next time you log in you will be asked to add the host to known hosts again.