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.
