No, you should not have to pay to get an SSL certificate rekeyed. Some providers may ask for money if you want to revoke the cert, if -- for example -- you believe your private keys may have been compromised and you want people's browsers to go nuts if they see that cert in the future, at (for example) a site attempting to MITM you.

Thanks!

This depends on which CA you're using. Some do not have a way to reissue/rekey at arbitrary times (StartCom, in particular), and charge for revocation. Most allow free reissue, and often don't charge for revocation and replacement issue.