All you need is an ssh key, which you can generate like this:

  ssh-keygen -f ca.key

Then you can generate certificates like this:

  # user key
  ssh-keygen -s ca.key -I key_id /path/to/user_key.pub
  # host key
  ssh-keygen -s ca.key -I key_id -h /path/to/host_key.pub

Secure ca.key according to whatever level of paranoia you desire. e.g. Passphrase, hardware security module (PKCS#12 is supported for generating certs), airgap the machine. anyone who gets access to ca.key has access to everything that trusts ca.key

Precisely this. From what I've read it isn't that easy to setup a CA.

Look into step-ca though, I've heard it's.. Okay? I don't know. It seems too complicated still - I'd rather stick with pubkey auth

Setup Hashicorp Vault. Almost easy but actyally hard to do right. Policies are easy to make too open and possibly insecure.