As mensagens de erro de / var / log / auth indicam que a instalação do ssh não foi concluída corretamente. As chaves do host não existem e sem chaves do host, o ssh não consegue iniciar a autenticação do usuário.
Você não menciona o sabor do Linux (redhat, debian, gentoo) e cada um tem uma estrutura de comando diferente para reinstalar o sshd.
Minha recomendação é desinstalar, reinstalar o daemon sshd no Linux e tentar novamente. Se você receber o erro da chave do host novamente, talvez sua distro exija que você crie manualmente essas chaves. Veja o arquivo readme para o sshd e isso deve guiá-lo.