I live right out side Albany NY so I don't know how much this will help you. I will say that my new route is 31 miles shorter and no NJ tolls. Time of travel is about the same.
Here goes:
NY Thruway I-87 south to
I-287 south to
RT 202/206 (Princeton, I think exit 17) to
Rt 1 to
I-295 south to
Rt42/55 Millville, NJ. This route is 271 miles for me. Use to be 300 miles with NJ tolls and god knows what kind of traffic on the NJ TPK. This route may work for you if you pick up the NY Thruway at the I-84/I-87 interchange (Newburgh, NY is 190 miles from NJMP). Only tolls from here would be going from exit 17 to exit 15. If this route adds to many miles, it may be cheaper to pay the man and tolls.
PS. You won't find this route using GPS. I get in a fight with my GPS every time I take this route.