Where did you get the 5000lb number from? If it's the empty weight, you could easily be up around 7000-7500lb when towing. If you are just guessing, run over the local CAT scale and find out what the real weights are.
When you say you "had to" slow down, did you ease up on the gas pedal or did the truck just slow down even though you were pouring on the coals? The 2.7L is good for 325HP but at 5000RPM so if you back off to keep the RPM down, you sacrificed HP.
5000RPM is within the engines operating limits, so with a new truck (assuming you broke it in already), there shouldn't be harm in running at 4000-5000RPM for 10-15min to get up a hill. You will be burning a lot of gas to keep 65-70mph up a steep grade.
PS: A 3/4 ton isn't typically much different in cost unless you push for the big diesel but