Um erro que você fez foi tentar iniciar sshd manualmente.
Se você, em vez disso, iniciar sshd por meios oficiais, isso deve funcionar. O comando service sabe qual é a maneira correta de iniciar um serviço em sua distribuição e isso deve funcionar:
service ssh start
No caso de scripts init sysv, é tudo o que você precisa fazer. A razão pela qual o diretório está ausente é que /var/run é um link simbólico para /run e /run é um ponto de montagem tmpfs . Isso significa que em cada inicialização /var/run começará vazia. Quando você usar o comando service , o script /etc/init.d/ssh será usado para iniciar sshd , mas antes disso, o script criará /var/run/sshd , se ele não existir.
Com systemd , as coisas funcionam de maneira um pouco diferente. Haverá um arquivo chamado /usr/lib/tmpfiles.d/sshd.conf com este conteúdo:
d /var/run/sshd 0755 root root
Durante a inicialização, isso deve fazer com que o diretório /var/run/sshd seja criado. O que você precisa para verificar se o arquivo existe e tem o conteúdo correto. Se o diretório /var/run/sshd ainda estiver ausente, você poderá verificar se ele é criado quando você executa systemd-tmpfiles --create manualmente.