Maybe (but I never tested) you can regenerate a certificate with the same couple public/private keys. If it does not work, unfortunately I think you will have to generate a new certificate. Do not forget to add the -validity <valdays>
option with a very large number of days. You will also have to change the package name as explained in this blog post.
UPDATE
According to @KIDdAe comment (see below), Google verifies the SHA1 fingerprint of the certificate and not only the certificate signature with the public key. Therefore recreating a new certificate with the same key is useless since the SHA1 of that new certificate will differ from the initial one.