Background
Amazon Linux 2 is approaching its End of Support (EOS) date, so I migrated one of our batch servers from Amazon Linux 2 to Amazon Linux 2023.
I reused the exact same SSH key pair when rebuilding the server, expecting the migration to be transparent. Instead, Rundeck (our job scheduling tool) started failing to connect to the node with this error:
Authentication failure connecting to node: "batch-server".
Make sure your resource definitions and credentials are up to date.
The confusing part: manually connecting to the same server with the same key, using the system's native OpenSSH client, worked without any issue. So the key itself was clearly not the problem — something else was going on.
Root Cause: Different Default SSH Algorithm Policies Between AL2 and AL2023
Rundeck server (Amazon Linux 2) Batch server (Amazon Linux 2023)
| OpenSSH version | Older | Latest |
| ssh-rsa (SHA-1 based signature) support | Enabled by default | Disabled by default |
| Default accepted algorithms | Includes ssh-rsa | Only SHA-2 based algorithms like rsa-sha2-256, rsa-sha2-512 |
Amazon Linux 2023 tightened its default SSH security policy and removed the SHA-1-based ssh-rsa algorithm from the default accepted list. This is a broader trend across the OpenSSH ecosystem — ssh-rsa has been considered weak for a while, and newer distributions are dropping it by default.
The catch is that Rundeck relies internally on jsch, a Java SSH library, to make its connections. jsch's release we were using is old enough that it doesn't support the newer rsa-sha2-256/rsa-sha2-512 signature schemes — it only knows how to request the legacy ssh-rsa algorithm.
Since the batch server (AL2023) rejects any ssh-rsa request outright, the SSH algorithm negotiation fails on jsch's end. Rundeck doesn't surface this nuance — it just reports a generic "Authentication failure," which is misleading if you don't already suspect an algorithm mismatch.
The key insight: the system's native OpenSSH client automatically negotiates the newer rsa-sha2-* algorithms and connects successfully, while jsch only speaks the older algorithm. So the same key, against the same server, produces different results depending on which SSH client library is doing the connecting.
How to Confirm
Check which public key algorithms the batch server's sshd actually accepts:
sudo sshd -T | grep -i pubkeyaccepted
If ssh-rsa is missing from that list, this is very likely your issue.
The Fix
On the batch server (AL2023), add the following line to /etc/ssh/sshd_config:
PubkeyAcceptedAlgorithms +ssh-rsa
The leading + matters — it appends ssh-rsa to the existing accepted list. If you omit the +, you'll overwrite the entire list and end up allowing only ssh-rsa, which weakens your SSH security posture more than intended.
Apply the change:
sudo sshd -t # syntax check
sudo systemctl restart sshd # restart (not reload)
sudo sshd -T | grep -i pubkeyaccepted # confirm ssh-rsa is now included
One gotcha to watch for: Amazon Linux 2023's /etc/ssh/sshd_config includes Include /etc/ssh/sshd_config.d/*.conf at the very top of the file. Since sshd applies the first matching directive it reads, if any file inside sshd_config.d/ already sets PubkeyAcceptedAlgorithms, your addition at the bottom of the main config file will be silently ignored. It's worth checking for this ahead of time:
grep -r -i "PubkeyAccepted" /etc/ssh/sshd_config.d/
Result
After the change, sshd -T output confirmed ssh-rsa was included in the accepted algorithms, and Rundeck was able to authenticate to the batch server again.
Takeaway
The strange part of this issue wasn't the fix itself — it was the "same key, same server, different result depending on the client" symptom. The real cause turned out to be a mismatch in SSH signature algorithm support, triggered by AL2023's stricter security defaults.
If you're migrating servers as part of an EOS response, it's worth checking upfront whether any external tooling that connects over SSH (Rundeck, Ansible, Jenkins, etc.) relies on an older SSH library under the hood — and whether that library supports modern signature algorithms. Otherwise you may hit the exact same wall after the migration is otherwise complete.
