Se for possível, e você não é dependente de ssh (você tem acesso físico à máquina), tente desinstalar o openssh-server, atualizando e reinstalando:
sudo apt-get remove openssh-server openssh-client --purge && sudo apt-get autoremove && sudo apt-get autoclean && sudo apt-get update
sudo apt-get install openssh-server