Supondo que você instalou openssh-server , verifique os links simbólicos de inicialização sshd nos diretórios /etc/rc{2,3,4,5} , execute ls -l /etc/rc?.d/*ssh
se não houver links de inicialização, crie-os executando:
sudo update-rc.d ssh defaults
e reinicie.
Se o problema ainda não foi resolvido, você pode tentar colocando service ssh start (antes da linha "saída 0")
no arquivo /etc/rc.local e reinicie novamente.