[tialaramex]

So there are three different scenarios wrapped up in this question and they're all interesting.

A. The server is new, and I'm setting it up presumably remotely e.g. in "the cloud". Ideally the autonomous setup should provision keys for me in this case, since they're public it's fine to even publish scripts which do this. However it's true that there are a lot of systems out there which instead give you a password for first login (or worse they have a fixed default!) which is sad.

B. The server has existing users, but not me. If we're not using certificates then I need an existing user to authorise me to use the machine, providing public keys is no different than anything else they might fill out, like my name, they will need a trustworthy source for all of it. For systems I have no other prior relationship to beyond that I am, as you see, tialaramex, I tell them to add the github keys for tialaramex, which are of course published. I will replace those after successfully connecting to their SSH server.

C. I've used this server but not from this machine. FIDO resident keys solve this (you can extract the resident key to a new client from your physical device, the device still needs to be present to actually authenticate) but I will also use SSH to connect to my home bastion and have that authenticate while I do setup once. I can SSH from my phone, so if this can't work then somehow I don't have my phone or access to my home, setting up SSH keys is a low priority in that case.

However it's true that none of this is yet ordinary.