ssh-rsa is in the default list of PubKeyAcceptedKeyTypes. Updating openssh has nothing to do with ssh-rsa now being disabled. So it’s either:
You have set a crypto policy that forbids ssh-rsa, such as FIPS or FUTURE, or created a modified crypto policy that changes the values
You have disabled crypto policies in openssh and modified sshd_config with that option and your own values, thus removing ssh-rsa
You have two choices. Either, generate an accepted key that is not ssh-rsa (e.g. ssh-keygen -t ed25519) or reset your crypto policies back to the default.
First a note: copy-pasted text is easier to obfuscate without photo-edit.
Host keys are not the same as user keys.
The (remote) host has some ssh_host_*_key. On first connect you accept and store corresponding *_key.pub into your (local) ~/.ssh/known_hosts. On future connects this is used to check whether you are again connecting to same (known) remote – a check against man-in-the-middle attack.
You did generate id_ed25519 user key that is in local machine. If you append the id_ed25519.pub into ~/.ssh/authorized_keys of the remote account, then you could authenticate with that to the remote.