How do you advise changing an IPSec L2L VPN pre-shared key with respect to minimizing downtime? Is there any magic formula for this, or best practice, or do you just kind of try to change it on both ends as closely as possible?
You didn't mention the implementation you're using, so I can't get too specific. But, the PSK is only used for initial authentication and session key management. After that, it's never used again (except reconnecting, which is really just starting a new session). Some implementations allow you to change the PSK without restarting the daemon, others don't.
If you have to change it on some sort of regular basis, you probably shouldn't be using PSK anyway; you should be using certificates.