This error happens when using Android 8.1 or bleow images: they use an old version of ssh server which requires extra settings when using OpenSSH >= 8.8 ssh clients.
Note
This should not happen with Android 9.0 or higher. If this is the case, it probably means that your instance is using an image from an old version of Genymotion Device Image (<13.2.0). Please upgrade your instance(s) to ver.14.0.0 or higher if possible: new releases include important bugs and critical security fixes.
Alternatively, you can workaround this issue by adding the options -o HostKeyAlgorithms=+ssh-rsa -o PubkeyAcceptedAlgorithms=+ssh-rsa to your ssh command.
For example:
ssh -i key.pem shell@3.252.167.165 -o HostKeyAlgorithms=+ssh-rsa -o PubkeyAcceptedAlgorithms=+ssh-rsa
You can also add the following in your ssh config file, /etc/ssh/ssh_config :
HostKeyAlgorithms = +ssh-rsa
PubkeyAcceptedAlgorithms = +ssh-rsa
Another option is to use a different algorithm when creating your key pair.
Please refer to your Cloud provider documentation for supported algorithms.