Certifique-se de que o openssh-server esteja instalado. Se já estiver instalado, tente reinstalar da seguinte forma:
sudo apt-get remove --purge openssh-server
sudo apt-get install openssh-server
Para o Ubuntu 16.04 LTS, não há nenhum problema com o kernel 4.4 e o kernel Linux 4.6 também é compatível. Se você ainda tiver o problema, recomendo que você atualize seu kernel ou recompile seu kernel.