Você ainda tem o código fonte? Se sim, recompila ele com uma nova key e republica ele na google play. Infelizmente, não tem o que fazer nesses casos... Quero dizer, talvez no console do googleplay console tenha para você exportar sua chave, mas, duvido muito