Updating larger numbers of SSL certificates and keys

We have an internal CA to sign certificates for non-public sites (and we got a few hundred virtual servers). When this CA was setup, keys were generated with MD5, which is considered insecure and browsers like Chrome and Firefox 16 are now rejecting these sites. So I have to regenerate keys and certificates with a new signature.

So I am looking for a way to automate this. I have done a little both with SOAP, but I wanted to check first with you experts which way you would do this. I can via a scrip scp the new certs and keys into /config/ssl, then I need to reload the ssl client profiles and finally sync it to the HA partner. We also use multiple partitions.

So .. how would you do that?