should I change gears or tranny???

One of the tire charts shows this tire is 31.7" tall, with 4:10s should give you 3042 RPM at 70 MPH

Now that is almost EXACTLY the same RPM my old 70 RR ran, and it would get just under 14 mpg with the sixpack engine (headers, Holley 800) and later would just nudge over 17 - 17.5 with a 340 in the car (headers, Thermojunk/ Quadrajet)

I won't dispute that an overdrive/ gear change may help, but if this thing is carrying a lot of cargo on these trips, too much OD may hurt as much as it helps, IE very little or no gain due to weight of cargo versus drop in RPM.