Let's say my signing key has been compromised and I have to revoke it.
What happens to the changesets and tags already signed? Should I rewrite them with the new signing key?
What happens to the changesets and tags already signed?
Nothing will happen to them - they remain signed, but with the revoked key. Revoked keys stay on keyservers (and on people's disks, if they have a local copy), so the signature can still be verified.
Should I rewrite them with the new signing key?
That depends on what you want to achieve, but probably yes. The whole point of signing tags is to certify "I (rather: the onwer of the private key) really created this tag."
By revoking your key you are effectively saying: "Don't trust any signatures with this key, they may be forged." So if you want to give users of your repository a way to verify the authenticity of tags, you should re-sign them.
You cannot re-sign a tag in Git, because the signature is an integral part of the (signed) tag. For details see for example Can I sign a git tag after it was created? on stackoverflow.com.
You will have to create a new tag, and sign it with your new key. Also note the general caveats about changing/replacing tags: You will either have to create the tag with a new name, or replace the existing tag. If you do the latter, people who previously fetched the old tags will have to manually delete them, otherwise they will not get the new tags.