Seems like simply issuing a warning on key creation "this key uses a newer, safer encryption scheme but as a result might not be directly portable to older vers

Seems like simply issuing a warning on key creation "this key uses a newer, safer encryption scheme but as a result might not be directly portable to older versions of openssh, if that's an issue use <someflag> to use the older, weaker scheme instead" would probably solve the problem in 99% of the cases. After a few years you might remove the warning and move on. For this type of applications security should trump backward compatibility, especially when in this case the breakage is fairly limited and easy to work around.