Você poderia tentar um vacuum verbose analyze? Isso também se aplica a você, @eboehnisch. A seguinte consulta muito simples, que leva em média 2s, é realmente estranha:
Como mencionado no tópico Atualização do PostgreSQL 12, gerar estatísticas é uma boa ideia após a atualização.