Como você observou, a caixa Fedora na qual você está efetuando login não foi configurada para permitir autenticação por senha, somente autenticação de chave pública - isso pode ser visto no resultado ssh -v
.
Portanto, uma solução é adicionar autenticação de senha, como você fez.
O outro método seria pegar o conteúdo de ~/.ssh/id_rsa.pub
na caixa do Ubuntu e adicioná-lo ao arquivo ~/.ssh/authorized_keys
na caixa do Fedora.
Agora que você tem a autenticação por senha ativada, é possível instalar a chave autorizada com este comando na caixa do Ubuntu:
$ ssh-copy-id fedora_box