Why is ADD CONSTRAINT ... NOT VALID taking a long time?
The ALTER TABLE needs an "access exclusive" lock on the table.  While it will only hold that lock for microseconds once it does gets it, it still might block indefinitely while waiting to acquire it if any other session is already holding any lock on the table.  And once it does block then other sessions, even ones wanting a weaker lock, will block behind it.  (PostgreSQL does not allow queue jumping, so a strong lock which is waiting to get granted will block incoming weak locks, even if those incoming locks would be compatible with the lock already being held.)

If you want the ALTER TABLE to either succeed or fail nearly instantly, set lock_timeout to a low value.  Trying to run them as separate statements would make the situation worse, not better.