My read of the output in the post when they tried to SSH to the device was that Tesla are actually doing the right thing here and using an SSH certificate authority, which allows issuing certificates signed with a private key authorising access to a subset of devices (optionally for a defined period of time). https://en.wikibooks.org/wiki/OpenSSH/Cookbook/Certificate-b... has more information, but in summary unless the private signing key is compromised in some way this is entirely legit. I'd hope that they also have some mechanism for distributing a new public key if the signing key does get compromised but who knows.

Not necessarily. All they have to do is roll a pub key into the update package. Same as any OTA update.

Why can't they rotate ? having root ssh keys on the device doesn't imply the certs don't rotate.