Crypto-period for keys used in PRF
You don't need to change the key at all in terms of it being "overused". The only reason to change a key is when you use it beyond the bounds given in proofs of security. You have to look this up, but if you are using HMAC-SHA256 with a 256-bit key then you can go on for about $2^{128}$ computations, which you will never every do.

Having said that, the reason to replace keys is because of the fear that they may be stolen by adversaries breaching your network. This has nothing to do with crypto, but is related to other risks.