How can I ssh into a server securely without knowing its key?

When I try to ssh into a remote server for the first time, I’m told that the authenticity of the host can’t be established. The recommended way to address this is to find out the host’s key via some other secure channel and add it to my known-hosts file. But this is a bad solution, because A) it means I lose the ability to ssh into that server if I’m ever on any other computer, and B) it forces anyone connecting to the server to do the same steps, wasting everyone’s time and increasing the possibility of human error.

TLS has already solved this problem. When I go to https://example.com, we trust some third-party certificate authority to say “yes, that key really is owned by example.com”, and now I can be confident that I am communicating with example.com, without needing to go through any burdensome manual verification process.

How can I set something like this up for a server that I own, such that I can ssh into it from any device using only my password, without having to remember or store a separate key?