I have created an Ubuntu droplet (via Laravel Forge if that matters) and am trying to remote connect to MySql using Navicat. I have installes by SSH key and am able to connect via SSH. I am also able to log into MySql...
Ok, here is the solution:
Enable the correct Kex:
sudo nano /etc/ssh/sshd_config
append with these lines to ensure correct digest: