This is probably not openssl but openssh related.

Just tried the same with up-to-date RHEL6.9 and it looks like it works for me. Can you provide your debug logs from the following command:

$ ssh -vvv fedora_username.org test

What is the version of openssh?

$ rpm -q openssh

Created attachment 1279007 [details]
stderr of ssh -vvv tgl.org test

(In reply to Jakub Jelen from comment #3)
> Just tried the same with up-to-date RHEL6.9 and it looks like it works for
> me. Can you provide your debug logs from the following command:
> $ ssh -vvv fedora_username.org test

Attached.  Looking briefly at the log, it seems odd that it's complaining about
my key file; "openssl rsa" recognizes the file as a passphrase-protected RSA key
without any problem.  But maybe that's unrelated.

> What is the version of openssh?

openssh-5.3p1-122.el6.x86_64

Thank you for the information.

> debug2: key_type_from_name: unknown key type 'ssh-ed25519'

It complains about the ed25519 host key (this type is not known to RHEL6 yet) that is being send by the remote server from pkgs.fedoraproject.org (RHEL 7 equivalent) as part of the SSH_MSG_KEX_DH_GEX_REPLY. IMHO, that key type signature should not be send in the first place, since it is not negotiated in the client PK_ALG proposal:

> debug2: kex_parse_kexinit: ssh-rsa-cert-v01,ssh-dss-cert-v01,ssh-rsa-cert-v00,ssh-dss-cert-v00,ssh-rsa,ssh-dss

but even server does not offer this PK_ALG in its proposal:

> debug2: kex_parse_kexinit: ssh-rsa,ssh-rsa-cert-v01


I am able to reproduce the behavior against this server now I am able to workaround the problem by telling the client that I really want RSA host keys (so at least it does not render rhel6 completely unusable):

ssh -o HostKeyAlgorithms=ssh-rsa -vvv jjelen.org test

This can be stored in the ~/.ssh/config as a workaround:

    Host pkgs.fedoraproject.org
      HostKeyAlgorithms ssh-rsa,ssh-rsa-cert-v01


But still I can not reproduce the same against my RHEL7 machine. 

From my point of view, this is some bug in the server (either implementation or configuration), but I will probably need more information how is it configured. I will have a look into that.

Thanks, I confirm that the HostKeyAlgorithms workaround works for me.
But it does seem like the server is doing something wrong.

Respective log from RHEL7 machine looks like this:

  debug1: ssh_ed25519_verify: signature correct
  debug1: Server host key: RSA-CERT fe:2e:6a:86:f3:41:e7:03:95:ea:9c:7f:75:9c:ce:9d
  debug3: load_hostkeys: loading entries for host "pkgs.fedoraproject.org" from file "/root/.ssh/known_hosts"

There is obviously some ed25519 in action, even though it is RSA-CERT. It is the certificate authority using ED25519, which was used to sign the RSA host key. This confuses the old clients and well ... there is no switch to negotiate certificate authorities key types (having that would be very over-engineered).

What can be done?

 * OpenSSH should not send certificates signed by the keys that are not supported by the peers (fix for RHEL7+)

but I am not sure how upstream will be willing to accept this change: interoperability between 5.3 (with backported certificates) and 7.5. Lets see.

 * There is no reasonable thing we can do about that in RHEL6 client. The server sends the host key based on key types that were negotiated (certificates have priority over keys). Ignoring the certificate is probably not what is expected.

 * Fedora release-engineering should be notified about this issue, but I don't expect they would re-issue the CA key to support RHEL6 clients.

>  * OpenSSH should not send certificates signed by the keys that are not
> supported by the peers (fix for RHEL7+)

This is not possible -- the key exchange expect that both client and server select the same PK_ALG and therefore server can not send raw RSA key if RSA_CERT is first in the supported list.

Upstream comment to this issue:

http://lists.mindrot.org/pipermail/openssh-unix-dev/2017-May/036032.html

Well, this is a problem, but we don't have a sane way to fix it in RHEL6 nor RHEL7. This is an addition to the protocol, which is not known to the old clients. The solution will be probably not to use this type of keys in infrastructure where RHEL6 should be supported.

Filled a releng ticked:
https://pagure.io/releng/issue/6798

Since there is no reasonable way to resolve this in RHEL6 nor upstream, I will close this bug and keep it tracked in Fedora releng Issue. Lets see what they can do about that.