I had a similar case and I got the EXPLAIN plan of the delete using:
EXPLAIN (ANALYZE, BUFFERS, TIMING)
In my case I detected that one trigger executed to check one FK was taking a lot of time.
Planning Time: 0.074 ms
Trigger for constraint fk_preparation_brochure_publication_profile_mapping_brochure_id: time=0.239 calls=1
Trigger for constraint preparation_brochure_custom_linkout_brochure_fk: time=3.737 calls=1
Trigger for constraint preparation_brochure_linkout_mapping_brochure_fk: time=18901.130 calls=1
Trigger for constraint fkks411c7rnuajq50lxutlfjygb: time=26.569 calls=1
Trigger preparation_brochure_history_trigger: time=37.139 calls=1
Execution Time: 18972.871 ms
Finally I found the reason: the original column was type varchar(200) and the referenced column in the FK was var(200).
Once I have aligned the referenced column with the type of the original one the deletion of the row was decreasing from around 20 seconds to few milliseconds.