I would look into your libssh, that is most likely one source of issue. If you do scan from outside INTO or from inside OUTOFF AWS i would strongly suggest to read the T&C from AWS to check if you are legally allowed to do what you plan to do.It might be not an Greenbone or a Issue with you SSH keys it could be a issue with the AWS infrastructure as well
All of the servers I’m trying to scan have the latest packages installed. Or did you mean libssh on the OpenVAS server?
I run the scans within the same VPC (same network) as the EC2 instances I’m trying to scan. I used to submit request forms to Amazon before running the scans, but that link you shared specifically says, “Effective immediately, AWS customers are welcome to carry out security assessments or penetration tests against their AWS infrastructure without prior approval for 8 services.”. EC2 is one of those 8 services.
Most likely your operating system is providing an outdated version of the libssh library not supporting some of the algorithms enforced by the remote SSH service (e.g. more recent SSH server versions, hardening of the sshd_config of the remote service, …).
The following VT should give you a brief overview over the supported algorithms by the remote host and which prerequisites (minimum libssh versio, build against a specific library, …) are required: