This error happens because you are using an old version of Genymotion Device Image: these images use an old version of ssh server which requires extra settings when using OpenSSH >= 8.8 ssh clients.
Warning
Please note that SSH retro-compatibility with old ssh servers may break in the future. We strongly recommend moving or upgrading to Genymotion Device Image ver. 13.2.0 images or higher, when possible, to avoid any compatibility issues.
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.