[Obrigado leonbloy e Bratchley]
Usando strace eu comparei com a saída de trabalho do fedora com centos. Ambos pareciam quase iguais. (Corrigido alguns problemas com a rede pensando que este poderia ser o motivo).
Analisou o código-fonte
http://www.opensource.apple.com/source/OpenSSH/OpenSSH-74/openssh/key.c.orig?txt
que apenas chama de openssl libraray. Então, tentei diretamente gerar os certificados rsa usando o openssl.
Isso me deu um erro que apontava para
' link '
Adicionando a variável de ambiente
export OPENSSL_ia32cap=~0x4000000000000000
Corrigido o problema.