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"

...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.