Also, make sure you're navigating to the supercharger... (although I could be an idiot, and that could be something that only works with newer cars)
So you have a 75D, I'm assuming? That would have been 238 new, so you're dealing with about 8% of battery degradation? If it's a 90D, that would be more like 14% degradation.
Assuming a 75D, I don't think replacing the battery will do much. The new battery would have the same type of chemistry, you'd still charge at the same speeds: I'd suggest instead trying to maximize the charge speeds.
* Use the computer to navigate to the supercharger to get the software to precondition the battery on route. Usually this will just mean use the Tesla navigation to plan your journey, but if you know you need an extra stop, make sure you put it into the Nav as soon as you're on the road to it.
* Prefer to avoid charging much above 65% at a supercharger. Charge at home for the 90% charges, but on the road get enough to get to the next stop, and go. Don't wait for 90%. Aim to arrive at the next supercharger at only 20%.
To take your Orlando example, 85 miles would be 38% or so? So the charge from 38% to 56% took 40 minutes? Here's a link to someone else's charging curve for a 75D Model X:
75D July 2018 build. What rate of charging at a Supercharger? ... notice that it's above 100kW only from 18% to 38%. If you pull in at 38%, even with a perfectly hot battery this would tell me to expect only about 90kW, dropping to 60kW by 60%. Bad Napkin math estimates it would take about 10 minutes on a hot battery to charge from 38 to 56.
40 minutes does seem slow... That would imply an average of 18kW charging speed. I'm guessing you didn't put the supercharger into navigation, or it didn't take long to get to it? (in my M3, it takes about an hour for the pack to fully heat up while driving)
If navigating to the supercharger doesn't make cause something about preconditioning your battery to show up on the nav screen, then the other option you have for heating up the battery is called "Yo-Yoing", where you do acceleration/regen braking/accelerate hard/regen brake hard loops. But ... that can be unsafe to do on public roads, and any passengers you have will NOT be amused.
I believe most of the slow-supercharging is pretty inherent to the car/battery, and replacing the battery won't fix it... but if it's that slow even if the battery should be warm, talk to service anyway.