My security department insists that I (the system administrator) make a new private key when I want a SSL certificate renewed for our web servers. They claim it's best practice, but my googling attempts have failed to verify their claim. What is the correct way?

The closest I've found is Should I regenerate new SSL private key yearly?, but it doesn't really explain why it would be necessary to change the keys.

I know it's not a big deal to change the keys while I'm at it, but I've never been one to just do what I'm being told without a proper reason or explanation :)

I would say that their suggestion isn't a very solid one, unless you're using horrifically small key sizes - in which case you have a different problem altogether.

A 2048-bit key, by most estimates, will keep you safe until at least the year 2020, if not longer than that. If you're running with 1024-bit keys or less, you're below the standard, and I recommend updating to 2048-bit immediately. If you're currently using 1536-bit keys, you should be safe for a year or two.

Of course, this is all academically speaking. The likelihood of someone being able (or inclined) to crack your 1024-bit SSL key within a year is extremely low.

As mentioned in the question you linked, there are benefits and drawbacks.

Benefits


Gives an attacker less time to crack the key. Somewhat of a moot point if you're using reasonable key sizes anyway.
Halts any evil-doers that may have compromised your private key. Unlikely, but unknown.
Gives you a chance to increase your key size to be ahead of the curve.


Drawbacks


Doesn't really give you any concrete protection against key cracking unless you're using terribly small keys.
SSL checking / anti-MitM plugins for browsers might alert the user that the key has changed. This is, in my opinion, a weak drawback - most users won't be using this.
Might cause temporary warnings in relation to more strict HSTS policies and implementations.
It requires work. You could be doing something else.


So on both sides there are some weak reasons, and some corner-cases you might need to consider. I'd lean slightly towards the "don't do it unless you need to" angle, as long as you're using 2048-bit keys or higher.

The most important thing is to ask them why they think it's necessary - it  may be that you have an infrastructure-related reason for updating the keys which we don't know about. If they can't come up with a solid argument ("why not?" isn't really valid) then they should probaly re-evaluate their advice.
