I had an 05 f250 with 6.0 that I towed our old trailer (about 13.5k pounds) with. Had airbags on it as well. No real issues other than I was technically overloaded (f250s and f350s are the same truck with the 250 being de-rated on its GVWR for registration purposes) and always felt the semis wake as they passed by. You can do it as I did but you'll want more truck if you plan on longer trips. I ended up trading the f250 for an 06 f350 drw with 4.10 gears.
My f250 had a higher tow rating than yours. I think I'd be looking for another truck, but that's just me. You don't need a "new" truck, just a newer one imho.
2016 North Point 377 RLBH
2006 Ford F350 Lariat, CC, 6.0PSD, DRW, SCT tuner, air bags, bullet proofed