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 time varchar(200) and the referenced column in the FK was var(200).

Once I have aligned the referenced column with the time of the original one the deletion of the row was decreasing from around 20 seconds to few milliseconds.