Are you autovacuuming and analyzing aggressively enough? Is there bloat or
other concern for these system tables? I expect it may be a concern based
on what I remember about your environment having thousands of tables and
perhaps autovacuum not keeping up (re: Too slow to create new schema and
their tables, functions, triggers).
Can you check results for last (auto)vacuum and analyze?
select * from pg_stat_all_tables where relname IN( 'pg_class',
'pg_attribute', 'pg_index' );