This is incorrect. SSH certificates work just like x509 certificates in that regard. Also, with PubkeyAuthentication, there exist all kinds of ways to collect host keys before connecting to them for the first time and thus avoiding the trust-on-first-use problem. Especially in private networks where you control all the nodes.