Oracle 12c - Slow query to tables ALL_CONS_COLUMNS and ALL_CONSTRAINTS
Sounds like statistics on those tables are out of date.  I would invoke the following statements:

purge dba_recyclebin;
exec dbms_stats.gather_dictionary_stats
exec dbms_stats.gather_fixed_objects_stats;


If your application creates and or drops tables frequently, you may need to put the above statements in a scheduled job.

And as @MarkDPowell suggested, you should also consider gathering system stats via DBMS_STATS.GATHER_SYSTEM_STATS and DBMS_STATS.GATHER_PROCESSING_RATE (new in 12c) -- that is important in 11g and more important in 12c.