Você diz em sua pergunta que você tem ufw permitindo todas as conexões de saída. Adicionar uma chave seria uma conexão de entrada em minha mente. Execute o seguinte comando no seu servidor para abrir a porta 22 para a entrada.
Sudo ufw allow 22
Em seguida, reinicie o ssh
Sudo service ssh restart
E tente importar sua chave novamente. Além disso, você pode querer considerar mover o ssh para uma porta alternativa.
Faça login no seu roteador e verifique se você tem a porta 22 encaminhada para o ip interno correto. Além disso, se você estiver se conectando externamente, verifique se o seu ISP não está atribuindo seu endereço IP dinâmico '. Caso contrário, o endereço estará mudando constantemente e você precisará usar um serviço como o dyndns.