Traveling with multiple horses is not unheard of, but not so much for this reason
In Europe, many wealthier knights traveled with 2 or more horses, but they did not switch off like this. They would have one large riding horse called a Palfrey that would carry the rider while traveling. On top of that, they would often have additional draft horses called Sumpters that would act as pack animals or pull the supply carts. These two kinds of horses were not the fastest, but they were well bred to carry the weight of a rider or supplies over very long distances. Then they would have a smaller, faster warhorse called a Destrier that they would only ride in battle. Because the draft horses were bred for endurance, and the warhorses for speed, the warhorses would be just as worn out after a long day's march as the draft horses. This means even if you had multiple Palfreis, switching off would be highly impractical because the Sumpters and Destriers still could not be driven any harder.
Another example is the Huns. They often traveled with many more horses than soldiers. While they would have changed mounts as they traveled, that was not the point. Hun soldiers often traveled with minimal provisions and lived off of the blood and milk of the horses. Any breast feeding mother will tell you that producing milk is a lot of work, and having to do that on top of exercise is quite exhausting. Having more horses meant your horses would not fatigue as quickly from having to put out the extra calories necessary to feed the rider. At the end of the day though, any animal will have tired, achy feet after a long walk with or without a heavy load.
How multiple horses can make you faster
When you do hear about switching out horses to increase speed, you are typically referring to the use of waystations on a road where people frequently need to travel in both directions quickly; so, you keep stables every few miles apart so that as a rider gets from one station to the next, he leaves his horse at the station to rest and picks up a fully rested horse to continue with. In this case, you only have 1 horse with you at a time, but you may easily end up riding 3 or more horses in a single day. These systems were most often seen used by courier or postal services such as Pony Express to expedite messages, and would allow a rider to cover MUCH more ground in 2 days than they could with a single horse.
Based on various sources, most agree than an average horse can sustain about 30 miles per day. In contrast, using way stations and fairly average horses, a rider can generally cover anywhere from 75 to over 200 miles per day depending on how the stations are spread out.
Now for your specific case
Note in the previous paragraph, I mentioned that the average horse can do 30 miles in a day. It is important to remember that horses are animals, not cars.
Imagine you have two people. One is your run of the mill computer nerd, and the other is a professional athlete wearing a 25lb backpack. I don't know about you, but I'm putting my money on the slightly encumbered athlete in just about any sort of race.
While most horses can only do 30 miles a day comfortably, many horses specifically bred and trained for distance can comfortably average 50-60 miles a day. When pushed to the max, a quality endurance horse can do 100 miles in 24 hours, and many champion endurance horses can even do 100 miles in as little as 12-15 hours! In other words, a good horse with a rider is still a LOT better than an average horse with no rider. For this reason, taking extra horses is a bad idea. Assume you have a stable with 18 horses in it. If you take all 18 then your top speed is capped by the weakest horse in the group; so, you may not travel more than 15-25 miles per day as you constantly have to slow down to let Ol'Bessy keep up with the group. In contrast, if you just take the 6 best horses, you will be able to push them much longer and harder even with riders because they will be tough enough to make up for the weight and then some.
