Ok, after trying the obvious myself I think I have figure out what was causing the issue.
"dnf upgrade" upgraded openssl version from 3.0.1-1.el9 to 3.0.1-12.el9
and the problem started after that.
After I downgraded the openssl back to 3.0.1-1.el9 and restarted Kerberos (systemctl
restart krb5kdc.service) the problem went away.
So it would seem the openssl is the root cause. Should I create a bug report or something
like that? (not really familiar with the process regarding this)