Você está confundindo certificados X.509 com chaves RSA. São implementações totalmente diferentes de PKI. Como tanto o cliente quanto o servidor SSH são membros do domínio, eu diria que esqueça as chaves e use o Kerberos / GSSAPI. Em /etc/ssh/sshd_config no servidor, você deve encontrar uma diretiva, GSSAPIAuthentication , descomentar e alterar o valor para yes . Reinicie o daemon SSH depois de salvar a mudança.
Para o cliente, você precisa do mais recente PuTTY (0.61) ou OpenSSH. O PuTTY tem o GSSAPI habilitado por padrão, então apenas digite o hostname do servidor SSH (o endereço IP irá não funcionar) e clique em conectar.