Description of problem:

Client is unable to connect to server using a certificate signed public key.

Client: Fedora 28 x86_64
libssh.x86_64                               0.8.2-1.fc28                @updates
libssh-devel.x86_64                         0.8.2-1.fc28                @updates
libssh2.x86_64                              1.8.0-7.fc28                @fedora 
openssh.x86_64                              7.8p1-1.fc28                @updates
openssh-askpass.x86_64                      7.8p1-1.fc28                @updates
openssh-clients.x86_64                      7.8p1-1.fc28                @updates
openssh-server.x86_64                       7.8p1-1.fc28                @updates

Server: CentOS 7.5 x86_64
libssh2.x86_64                     1.4.3-10.el7_2.1                    @updates   
openssh.x86_64                     7.4p1-16.el7                        @base    
openssh-clients.x86_64             7.4p1-16.el7                        @base    
openssh-server.x86_64              7.4p1-16.el7                        @base    




How reproducible:
Able to replicate following the steps. Each time is the same result.

Steps to Reproduce:
1. ssh-keygen -t rsa -b 2048 -f test
2. ssh-keygen -s cert.key -I "signedcert" -n testuser -O clear -O permit-agent-forwarding -O permit-pty -V -1w:+260w -z 0 test.pub
3. ssh -i test -vvv user@serverip

Actual results:
ssh -vvi key user@serverip                                                                                                               [10:35:37]
debug1: Offering public key: RSA-CERT SHA256:r7OlYvphkF6hsvFdWS2k1GsZVkNv60DCSAPMngN2lrs test
debug1: send_pubkey_test: no mutual signature algorithm
debug2: we did not send a packet, disable method
debug1: No more authentication methods to try.
user@serverip: Permission denied (publickey).


Expected results:
RSA-CERT SHA256:r7OlYvphkF6hsvFdWS2k1GsZVkNv60DCSAPMngN2lrs test
Would be accepted as authorized public key.

Additional Details:
Work Around:
Adding 
PubkeyAcceptedKeyTypes +rsa-sha2-256,rsa-sha2-512,rsa-sha2-256-cert-v01,rsa-sha2-512-cert-v01,ssh-rsa-cert-v01
into ssh client configuration does not allow authentication. 
At this time, the only workaround I have found involves signing the RSA key with ed25519. This is further supported by the following debug lines in the ssh connection:

Server Key Algorithms:
debug2: host key algorithms: ecdsa-sha2-nistp256-cert-v01,ecdsa-sha2-nistp384-cert-v01,ecdsa-sha2-nistp521-cert-v01,ssh-ed25519-cert-v01,rsa-sha2-512-cert-v01,rsa-sha2-256-cert-v01,ssh-rsa-cert-v01,ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,ssh-ed25519,rsa-sha2-512,rsa-sha2-256,ssh-rsa

Client Key Algorithms:
debug2: host key algorithms: ssh-rsa,rsa-sha2-512,rsa-sha2-256,ssh-ed25519

Negotiated:
debug1: kex: host key algorithm: ssh-ed25519

Thus, RSA is no longer supported as a signing key cipher.

Note:
https://bugzilla.redhat.com/show_bug.cgi?id=1623929
Addresses RSA Key failure authentication. This bug addresses RSA certificate signed keys.