I have found that a good cleaner, like PEC-12 is worth the trouble if you know the negs are dirty. It will remove, with little pressure, the stuff that it can dissolve. (use with cotton or a Webril pad).
You can also rewash in water and hang like new film, with Photoflo, or like material, to remove water-soluble stuff.
You can also try isopropanol, or rubbing alcohol. I would recommend the purest strength you can get. Rubbing alcohol can run from 70% into the 90's, and contains other materials. I ordered a gallon of isopropanol, which is 9x% purem from a local drug store some years ago. It removes other kinds of stuff. Research isopropanol if you decide to use it, for info on handling.
I have also used a 50-50 mix of isopropanol and distilled water to soak and gently massage (4x5) negs to remove long term issues such as mold, etc. - not always successful but sometimes, also will dry very quickly and evenly.
After any or all of this, I then would wipe them with an orange Ilford antistatic cloth.
I am good at working in PShop, but I have found the cleaning to be worth the time.