I’ve recently come across an interesting bug in Linux Mint. When trying to ssh to a Mint machine from OSX, I’d get errors saying “no hostkey alg“. After going on a long Google Vision Quest, I was still none the wiser. All the tricks I’d found didn’t work at all. The solution – at least for me – seems to be to purge the running openssh that comes as part of the install, followed by reinstalling it.
Reinstalling ssh remotely, over ssh, is a foolish thing to do. If there is no other option, then run the following command in a screen.
sudo apt-get purge openssh-server && apt-get install openssh-server
After the ssh server has remade its ssh keys and the daemon restarts, you should be able to ssh without any issue.