Being unable to connect to my VM instance I realized it was due to expired ssh keys. So I created a new public key and deleted the expired keys by editing the VM. After adding the new key, I was able to connect to the VM after a restart. However, as soon as the connection is made the expired ssh keys get re-added to the VM and prevent any further connection.
I understand, they must be stored in metadata somehow but I cannot find how to remove them and stop them from reappearing. Any help is appreciated.