A melhor maneira de fazer isso funcionar é instalar o pacote openssh-client (com as ferramentas do cliente) e o pacote openssh-server (com o daemon do servidor):
sudo apt-get install openssh-client openssh-server
Isso deve resolver seu problema.