However, if you do not need the extra features provided by certificates, using SSH-generated keys is strictly equivalent with using certificates and it requires less work.
TOFU is neither necessary nor recommended, it is just a convenience feature, to be used when security may be lax.
The secure way to use SSH is to never use TOFU but to pair the user and the server by copying the public keys between the 2 computers through a secure channel, e.g. either by using a USB memory or by sending the public keys through already existing authenticated encrypted links that pass through other computers. (Such a link may be a HTTPS download link.)
When using certificates, a completely identical procedure must be used. After certificates are generated, like also after SSH keys are generated, the certificates must be copied to the client computer and the server computer through secure channels.
Just to make it clear: this does not mean that it is fine to blindly accept the message on first use.
The "secure way" implies copying the server's public key as well, which people generally don't do, right? Which is equivalent to verifying the fingerprint shown with the TOFU message, correct?
The server public key must be copied into "known_hosts" on the client, while the client public key must be copied into "authorized_keys" on the server.
When this is the procedure that is always followed, any message shown by SSH about an unknown host means that the connection must be aborted, because the identity of the server is unknown.
You cannot truly verify the "fingerprint" displayed by SSH, unless you simultaneously have access to another computer, where you have a copy of the fingerprint. What is usually meant by "verifying" is that you remember a few digits of the fingerprint, and those match.
You could have copied the fingerprint from the server, to be able to truly verify it, but that does not make sense, because in that case you should have copied the entire key, not just the fingerprint, and you should have installed it in the client.
When you use only authentication with digital signatures, it does not make sense to use any other procedure, because you must make at least one of the two copies anyway, so when copying the client key to the server you can take the server key, to carry it back to the client.
The TOFU method is meant to be used together with password-based authentication, in less secure applications, where no physical access to the server is required for setting up SSH on the client.
By "less secure" I mean for example applications equivalent to HTTPS, where the client is not really authenticated, e.g. when providing a public password allowing read-only access to an SSH server through Internet.
Sure, I just wanted to make sure that nobody would understand "TOFU is neither necessary nor recommended, just ignore that message and say "yes" when it appears".
Both ends need to be sure of who is on the other end, and there are different ways to achieve that. The way SSH works is that if you haven't copied the server public key locally, it will explicitly ask you to verify it the first time.
I am not sure that "SSH does TOFU". SSH asks you to verify. The human who YOLOs it and approves it without checking is the one doing TOFU, and this is not really secure.
That is not the case, and is a major advantage of certificates.
As for your ISP I think you should never rely on TOFU over the public internet. If you really don't want to do ssh certs it's easy enough to make the host key available securely via https.