This all seems good advice for an organisation with fairly heterogenous client/server populations.

Seems also to work if you have only cutting edge SSH (since its split by modern/intermediate) which is nice

I set this up on my servers, and not a single Android ssh client was able to connect, or even read the keys generated on another device.

This seriously affects my confidence in the security of Android.

The intermediate setup should normally work for you, at least with some clients. Seems ok with JuiceSSH.