Unable to SSH to new Virtual Machine after upgrading the template to RHEL 8.7 or 9

Issue

• Unable to SSH to a Virtual Machine after upgrading it to RHEL 8.7, 9 or higher versions.
• During first boot, sshd fails to start on new Virtual Machines:

Nov 29 08:49:18 rhel8 systemd[1]: Starting OpenSSH server daemon...
Nov 29 08:49:18 rhel8 sshd[2946]: Unable to load host key: /etc/ssh/ssh_host_rsa_key
Nov 29 08:49:18 rhel8 sshd[2946]: Unable to load host key: /etc/ssh/ssh_host_ecdsa_key
Nov 29 08:49:18 rhel8 sshd[2946]: Unable to load host key: /etc/ssh/ssh_host_ed25519_key
Nov 29 08:49:18 rhel8 sshd[2946]: sshd: no hostkeys available -- exiting.
Nov 29 08:49:18 rhel8 systemd[1]: sshd.service: Main process exited, code=exited, status=1/FAILURE
Nov 29 08:49:18 rhel8 systemd[1]: sshd.service: Failed with result 'exit-code'.
Nov 29 08:49:18 rhel8 systemd[1]: Failed to start OpenSSH server daemon.