I recently have created an instance and not SSH shows an error after update

I have also faced this quite a few times and here is how you can overcome this:

Here is how you would do step by step:

   vi /etc/ssh/sshd_config

Press "i" to insert lines and add following two lines to this file:

   TrustedUserCAKeys /etc/ssh/lightsail_instance_ca.pub  

   CASignatureAlgorithms +ssh-rsa

Press Esc button and type wq and hit enter to save the changes to file.

Restart ssh service by one of the following ways:

    systemctl restart ssh

Or

   sudo service sshd restart

   sudo /etc/init.d/ssh restart

This should have fixed the issue and if you are still not able to ssh, then your public key file might have been corrupted and you'd need to run following command:

    cat /var/lib/cloud/instance/user-data.txt | grep ^ssh-rsa > /etc/ssh/lightsail_instance_ca.pub

When I faced this error, above steps worked for me but I also came across another approach and I tried that too with success, so I'm mentioning that here too:

1. Take snapshot of server

2. Create a new lightsail server from that snapshot

3. In the server creation process, you can reset PEM file(optional). Use the following start up script, which would be executed when server would be started:

        sudo sh -c "cat /var/lib/cloud/instance/user-data.txt | grep ^ssh-rsa > /etc/ssh/lightsail_instance_ca.pub"
        sudo sh -c "echo >> /etc/ssh/sshd_config" 
        sudo sh -c "echo 'TrustedUserCAKeys /etc/ssh/lightsail_instance_ca.pub' >> /etc/ssh/sshd_config"
        sudo sh -c "echo 'CASignatureAlgorithms ecdsa-sha2-nistp256,ecdsa-sha2-nistp384,ecdsa-sha2-nistp521,ssh-ed25519,rsa-sha2-512,rsa-sha2-256,ssh-rsa' >> /etc/ssh/sshd_config"
        sudo systemctl restart sshd