Did this just start happening suddenly?  With a server you'd connected to before?

What version of Absolute are you using?

If this just starts happening and you didn't change anything in the client config, it usually means something changed in the server configuration.  Newer servers will sometimes disable older less secure host key algorithms in favor of newer ones.  This can create a compatibility issues with older clients.  The server and client must negotiate an algorithm they both support and understand or you get the 'failed to negotiate' message.  This can be true of host key algorithms, key exchange, macs, encryptions, etc...

Can you try the latest version of 12.x from the website?  Many new algorithms are supported in the new client and probably take care of the issue.  You can download the demo for free at least to test out that theory.  If the server is internet-facing, email me the name or IP and I can see for myself.  Algorithm negotiation happens BEFORE authentication, so I could try that much at least without even trying to log in.

If you control the server, or know who does, you could also try re-enabling the host key algorithms that were disabled.

If any of this helps, let me know.

If not, we can keep digging.

Brian