Comment 5 for bug 1790963

This [1] appears to be the source of the problem, specifically "Add new RSA certificate types that that can be used in the above options and on the wire to require the use of RSA/SHA2 signatures." - unfortunately, those new certificate types don't exist/work in openssh <7.8, breaking backwards compatibility with 7.8 clients.

Christian - Correct, it doesn't matter that no Ubuntu version is shipping with openssh 7.8 today. Bleeding edge distributions are, and non-Linux users are getting updates to 7.8, which breaks connectivity to any openssh server <7.8 under these circumstances when the client is 7.8.

Etienne - Thank you for providing that - it is the current workaround aside from downgrading clients to 7.7. This is not a complete solution though, as it doesn't help for environments that sign RSA user certificates through an automated service (unless that service supports EC certs, which I'm going to guess may not work with really old versions of openssh).

[1] http://bugzilla.mindrot.org/show_bug.cgi?id=2799