I have tried to access control plane and worker nodes after provisioning (but I am unable to login because SSH public key I entered during provisioning is not configured on nodes which I described in another thread) so my host SSH key is recorded in my client for future use.

But after rebooting the node, host SSH key is changed:

[me@home ~]$ ssh -p 22 root@172.16.172.16
root@172.16.172.16's password:
Permission denied, please try again.
root@172.16.172.16's password:

reboot happens here

[me@home ~]$ ssh -p 22 root@172.16.172.16
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that a host key has just been changed.

Is that supposed to happen or is it because cloud-init is failing to configure nodes?

I don't think it is a good thing to change host SSH key every time node is restarted...