In D&D 5e, the daily rate of mounted overland travel is generally the same as on foot, because horses get tired and adventurers carry a lot of heavy equipment.
See the section Special Travel Pace in the DMG (p. 242–243). This section starts:
The rules on travel pace in the Player’s Handbook assume that a group of travelers adopts a pace that, over time, is unaffected by the individual members’ walking speeds. The difference between walking speeds can be significant during combat, but during an overland journey, the difference vanishes as travelers pause to catch their breath, the faster ones wait for the slower ones, and one traveler’s quickness is matched by another traveler’s endurance.
In the same section, the rule is:
- In 1 hour, you can move a number of miles equal to your speed divided by 10.
and then:
- For a fast pace, increase the rate of travel by one-third.
- For a slow pace, multiply the rate by two-thirds.
So an unencumbered horse with a speed of 60 could theoretically travel 6 miles in an hour at a normal pace. At a fast pace (a gallop), 8 miles per hour. That's "twice the usual distance for a fast pace", where "usual" means a creature with a speed of 30. This suggests that a riding horse with no rider, traveling alone, can cover 48 miles per day at a normal pace.
So the rule that "a mounted character can ride at a gallop for about an hour, covering twice the usual distance for a fast pace" seems to exist to allow for mounted travelers covering short distances quickly by using the mount's speed instead of "the usual pace", for up to an hour each day.
So, according to the rules, a traveler on a horse at a normal pace (3 miles per hour) will cover about 24 miles in an 8-hour day. If you make the horse gallop for an hour each day (fast pace for a horse being 8 miles per hour), that range increases to 29 miles. That's within the realm of what you would expect in real life, with a fast horse on good roads in fair weather.
Variant: Encumbrance
If you're using the encumbrance rule, a Riding Horse needs to be carrying less than 80 lbs of rider and equipment to get its full speed of 60. Loaded with between 80 and 160 lbs it has a speed of 50, and carrying between 160 and 480 lbs (its maximum carrying capacity) it has a speed of 30. A 200 lb adventurer in chainmail with a dungeoneering pack, longsword, and shield weighs in at about 325 lbs, so under this rule a horse's travel pace is usually the same as an unencumbered adventurer on foot.
From the Sword Coast Adventurer's Guide map made available from Wizards of the Coast. Phandalin is located in the northern foothills of the Sword Mountains, northeast of the Mere of Dread Men and south-southwest of Neverwinter. Greenest is located in the Greenfields, north of the Snakewood and south of Burdusk, its exact location within this largeish area is not specified.
Eyeballing this with the scale on the map gives a direct line distance of 1,000 to 1,200 miles (i.e. a bloody long way). For comparison this is approximately the distance between Los Angeles and Denver, New York and Orlando, London and Warsaw or Sydney and Melbourne.
Assuming that overland routes will be 25% further then you are looking at 1,250 to 1,450 miles. From the PHB p.182, normal pace is 24 miles a day - this is independent of the mode of transport, walking is slower per hours but a person can walk for longer than a horse can so it evens out in the end. This would take 52 to 60 days assuming no rest days - most caravans would rest 1 day in 7 so say 61 to 70 or 2 - 2.5 months.
Until the development of the railway, waterborne travel was much quicker than overland travel. Based on the figures in the PHB, a sailing vessel is 2-3 times faster than overland travel (since ships don't need to rest, they can travel for 24 hours a day). By traveling from Neverwinter to Candlekeep by ship you could probably shave 20+ days off the travel time even though the distance traveled is longer. Further, the Chionthar is navigable to Elturel saving another week or so and may be navigable to Berdusk - at least another 3-4 days saved.
Best Answer
I can improve on markovchain's answer by swapping a phantom steed for the wild-shaped druid. The phantom steed has a speed of 100 feet; we can improve this using the usual tricks (longstrider, transmuter stone, horseshoes of speed) to 150 feet, which means 15 miles per hour.
Like all creatures, the phantom steed can travel at +33% speed for a "fast pace" (this is what the line "or 13 miles at a fast pace" in the spell text means). This gives 20mph. markovchain offers two innovations: (1) an Elk Totem Barbarian can double this, and (2) the creature can "gallop" for one hour, which doubles this again. This gives 80mph.
Our phantom steed can gallop for only an hour, so we need eight phantom steeds to do this properly. If the DM rules that a horseshoes of speed can be reapplied to a new phantom steed very quickly, then our Elk Barbarian 6 can multiclass and take five levels of Transmuter Wizard, which will let her read the phantom steed spells from scrolls. She would need one scroll of longstrider and six scrolls of phantom steed in addition to her spell slots.
It's likely that the DM will rule that horseshoes of speed take significant time to put on a horse. (See: How long does your farrier take to shoe one horse?) If that's the case, then we need to assume the existence of courier stops, spaced every 80 miles along the route. Each courier stop would have a fresh phantom steed mount with the horseshoes already applied. Presumably a fifth-level wizard would supply the magic for each one.
80mph times eight hours gives 640 miles.
The above is a good practical solution. For completeness, I should note there are less practical solutions which are faster -- for example, with a line of friendly wizards, spaced 500 feet apart, with readied actions to cast dimension door on you, you can move arbitrarily far in one turn. There's also cheese involving fast mounting and dismounting, or even just a line of Giants with readied actions to pass you from one to the next.