A service may provision an account with a provided ssh public key, so that you never log in with a password, even once.
It's sort of a chicken-egg problem though, presumably you do have a password somewhere along the line, such as in a portal where you created your account and uploaded your public key.
I'd say there are more valuable things you can do to improve security than solving the problem of "having to ssh in with a password one time to upload a key"
Maybe. Not having a password on the server eliminates all the risks associated with weak or leaked passwords. And then you can configure SSH to reject password logins altogether. It's not an insignificant benefit.
I'd say there are more valuable things you can do to improve security than solving the problem of "having to ssh in with a password one time to upload a key, then updating the config to reject password logins".
SSH password login is secure. Keys are preferred since you can't have asdf1234 as a key, but if you as the initial person to set up the server are the only one allowed password login and use a decent password, you're fine
...Key-distribution is to encryption systems as cache-invalidation is to computer science. Both of which are subforms of the ur-problem of signal-propagation which itself is stemmed from the physical principle of causality.
Only way through it is to shut up and do it, sadly.
The implementation details of doing it are often either A) have physical possesion of computer, and do initial insecure setup within a "secure realm" you control, or B) redefine your "secure realm" to include the hardware being in someone else's possession, and do what they tell you and pray they are trustworthy.
It's sort of a chicken-egg problem though, presumably you do have a password somewhere along the line, such as in a portal where you created your account and uploaded your public key.