SSH failing with "ssh_rsa_verify: cannot handle type rsa-sha2-256"

I have an old Server (Centos 4 - yes it will be upgraded but not yet!) and a new Backup machine (Rocky 9.5). I previously had rsync from the server to a previous incarnation of the backup machine (Centos 8) working, but the backup server OS died (when I tried to update pacakges...). I want to use rsync -e ssh ... to mirror files from the Server to the Backup. The issue I have is in getting the two servers to talk over SSH. I have overcome most hurdles by adding into the Backup's SSHD config:

#Legacy changes
KexAlgorithms +diffie-hellman-group1-sha1
HostkeyAlgorithms +ssh-rsa
PubkeyAcceptedKeyTypes +ssh-rsa

That's overcome the initial hurdle of getting old (considered insecure, but this is on my own private network) protocols. But I can't figure out why the key's don't work. * On Backup I generated a new key that should be SHA1:

-sh
    ssh-keygen -t rsa -t ssh-rsa -f ssh_host_rsa_key

* I did also try with just -t rsa and just -t ssh-rsa. As per man ssh-keygen: > This flag may also be used to specify the desired signature type when signing certificates using an RSA CA key. The available RSA signature variants are ssh-rsa ... I was trying to use that to create a SHA1 rather than SHA256 signature. * But the Server fails to connect:

ssh_rsa_verify: cannot handle type rsa-sha2-256
    key_verify failed for server_host_key

How do I generate a key that the Server will be acceptable with? For info, the SSH version on Backup is OpenSSH_8.7p1, OpenSSL 3.2.2 and on ServerOpenSSH_3.9p1, OpenSSL 0.9.7a. Additional info, the response on the Server when attempting the connection (actual IP addresses changed to x.x.x.): [root@server ssh]# ssh -vvv x.x.x.5 root@backup OpenSSH_3.9p1, OpenSSL 0.9.7a Feb 19 2003 debug1: Reading configuration data /etc/ssh/ssh_config debug1: Applying options for * debug2: ssh_connect: needpriv 0 debug1: Connecting to x.x.x.5 [x.x.x.5] port 22. debug1: Connection established. debug1: permanently_set_uid: 0/0 debug1: identity file /root/.ssh/identity type -1 debug3: Not a RSA1 key file /root/.ssh/id_rsa. debug2: key_type_from_name: unknown key type '-----BEGIN' debug3: key_read: missing keytype debug3: key_read: missing whitespace debug3: key_read: missing whitespace debug3: key_read: missing whitespace debug3: key_read: missing whitespace debug3: key_read: missing whitespace debug3: key_read: missing whitespace debug3: key_read: missing whitespace debug3: key_read: missing whitespace debug3: key_read: missing whitespace debug3: key_read: missing whitespace debug3: key_read: missing whitespace debug3: key_read: missing whitespace debug3: key_read: missing whitespace debug2: key_type_from_name: unknown key type '-----END' debug3: key_read: missing keytype debug1: identity file /root/.ssh/id_rsa type 1 debug1: identity file /root/.ssh/id_dsa type -1 debug1: Remote protocol version 2.0, remote software version OpenSSH_8.7 debug1: match: OpenSSH_8.7 pat OpenSSH* debug1: Enabling compatibility mode for protocol 2.0 debug1: Local version string SSH-2.0-OpenSSH_3.9p1 debug2: fd 3 setting O_NONBLOCK debug1: SSH2_MSG_KEXINIT sent debug1: SSH2_MSG_KEXINIT received debug2: kex_parse_kexinit: diffie-hellman-group-exchange-sha1,diffie-hellman-group14-sha1,diffie-hellman-group1-sha1 debug2: kex_parse_kexinit: ssh-rsa,ssh-dss debug2: kex_parse_kexinit: aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,arcfour,aes192-cbc,aes256-cbc,rijndael-cbc@lysator.liu.se,aes128-ctr,aes192-ctr,aes256-ctr debug2: kex_parse_kexinit: aes128-cbc,3des-cbc,blowfish-cbc,cast128-cbc,arcfour,aes192-cbc,aes256-cbc,rijndael-cbc@lysator.liu.se,aes128-ctr,aes192-ctr,aes256-ctr debug2: kex_parse_kexinit: hmac-md5,hmac-sha1,hmac-ripemd160,hmac-ripemd160@openssh.com,hmac-sha1-96,hmac-md5-96 debug2: kex_parse_kexinit: hmac-md5,hmac-sha1,hmac-ripemd160,hmac-ripemd160@openssh.com,hmac-sha1-96,hmac-md5-96 debug2: kex_parse_kexinit: none,zlib debug2: kex_parse_kexinit: none,zlib debug2: kex_parse_kexinit: debug2: kex_parse_kexinit: debug2: kex_parse_kexinit: first_kex_follows 0 debug2: kex_parse_kexinit: reserved 0 debug2: kex_parse_kexinit: curve25519-sha256,curve25519-sha256@libssh.org,ecdh-sha2-nistp256,ecdh-sha2-nistp384,ecdh-sha2-nistp521,diffie-hellman-group-exchange-sha256,diffie-hellman-group16-sha512,diffie-hellman-group18-sha512,diffie-hellman-group14-sha256,diffie-hellman-group1-sha1,kex-strict-s-v00@openssh.com debug2: kex_parse_kexinit: rsa-sha2-512,rsa-sha2-256,ssh-rsa,ecdsa-sha2-nistp256,ssh-ed25519 debug2: kex_parse_kexinit: aes256-gcm@openssh.com,chacha20-poly1305@openssh.com,aes256-ctr,aes128-gcm@openssh.com,aes128-ctr debug2: kex_parse_kexinit: aes256-gcm@openssh.com,chacha20-poly1305@openssh.com,aes256-ctr,aes128-gcm@openssh.com,aes128-ctr debug2: kex_parse_kexinit: hmac-sha2-256-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha2-256,hmac-sha1,umac-128@openssh.com,hmac-sha2-512 debug2: kex_parse_kexinit: hmac-sha2-256-etm@openssh.com,hmac-sha1-etm@openssh.com,umac-128-etm@openssh.com,hmac-sha2-512-etm@openssh.com,hmac-sha2-256,hmac-sha1,umac-128@openssh.com,hmac-sha2-512 debug2: kex_parse_kexinit: none,zlib@openssh.com debug2: kex_parse_kexinit: none,zlib@openssh.com debug2: kex_parse_kexinit: debug2: kex_parse_kexinit: debug2: kex_parse_kexinit: first_kex_follows 0 debug2: kex_parse_kexinit: reserved 0 debug2: mac_init: found hmac-sha1 debug1: kex: server->client aes128-ctr hmac-sha1 none debug2: mac_init: found hmac-sha1 debug1: kex: client->server aes128-ctr hmac-sha1 none debug2: dh_gen_key: priv key bits set: 161/320 debug2: bits set: 512/1024 debug1: sending SSH2_MSG_KEXDH_INIT debug1: expecting SSH2_MSG_KEXDH_REPLY debug3: check_host_in_hostfile: filename /root/.ssh/known_hosts debug3: check_host_in_hostfile: match line 2 debug1: Host 'x.x.x.5' is known and matches the RSA host key. debug1: Found key in /root/.ssh/known_hosts:2 debug2: bits set: 513/1024 ssh_rsa_verify: cannot handle type rsa-sha2-256 key_verify failed for server_host_key