¿Podrías probar con un vacuum verbose analyze? Esto también aplica para ti, @eboehnisch. Es realmente extraño que la siguiente consulta muy simple promedie 2 segundos:
Como se mencionó en el tema Actualización de PostgreSQL 12, generar estadísticas es una buena idea después de la actualización.