I'm not sure if this is the best forum to ask this in, but does anyone know what causes a host key to change? This seems to keep periodically happening on a LAN of mine.

the key being deleted, often by the server being rebuilt. it'll not happen automatically.

I can only think of two ways for this to happen.

A sysadmin who doesn't understand SSH might upgrade a system without preserving the SSH host keys (and new ones will be generated by the new operating system install) or an incompetent sysadmin might delete or move host keys by accident. They are in /etc/ssh usually and need to have correct protections and ownership.

A malicious computer criminal might change the host keys so that man-in-the-middle attacks can be performed without anyone noticing. Your only protection against MitM is reliable, unchanging host keys. If your end users become accustomed to ignoring host key change warning messages, it opens up your whole infrastructure to MitM attacks.

Either way, you need to track this down. Host keys should be built strong (make them bigger than you need) and should never change without prior notification.

I've seen this as a symptom when a mis-configured DHCP server (and later a disorganised system admin) had assigned an IP address twice - once to my device, and once to another piece of equipment, also with SSH running. Depending on what ARP packets the switches had seen most rfecently, you got a system chosen at random ...

Looking up the vendor part of the remote MAC address (get it from an arp dump on your client) may provide some clues (it told me to look for a CISCO system as the culprit).
http://curreedy.com/stu/nic/
http://www.coffer.com/mac_find/
http://www.techzoom.net/tools/check-mac.en