Even at the pace you suggest, Envinyatar, let us take dark age/medieval marches into consideration, since Tolkien's works emanate from that rough time period. Historically, many of them take forever. But not because of distance necessarily. Most of this comes from the managing of supplies, the need to acquire travel, the mustering of troops, among other things. Also, we must consider that they would be traveling during the 'winter months', and most military operations do not take place in that time. Even elves would be wary of a winter march. Even under such dire circumstances, 'ancient' warriors would be unlikely to march in the winter, because it causes extra problems that often can't be dealt with in a timely manner.
So, I believe that setting out in late 1695 is both problematic, and unlikely. Under the circumstances, the beginning of spring for 1696, or possibly the fall of 1695, would be better. The weather is better suited to both marching and fighting, should it occur.
Just my thoughts...
