Created attachment 2757 [details] ssh -vvv output After upgrading from 6.9 to 7.1, CA-signed keys are broken. ssh fails to verify a CA-signed host key and fails to load/use a CA-signed user key. Attached output of ssh -vvv. Note particularly lines 9-10, 68-71.
The server in question is offering the legacy certificate format that was removed in OpenSSH 7.0 > debug2: kex_parse_kexinit: ssh-rsa,ssh-rsa-cert-v00@openssh.com,ssh-dss The legacy keys haven't been the default since OpenSSH 5.6. The remote version (OpenSSH 6.0) supports the current cert format fine, so regenerating your certificates should get you working.
Close all resolved bugs after 7.3p1 release