Besides the already mentioned moose, I'd suggest:
1. Bovines
While a bison's running speed (~55 km/h) rivals that of a horse (~50 km/h while galloping), I don't see the species beeing that easily tamed and domesticated for transportation (it hasn't been this far in human history for various reasons).
However, if your setting goes beyond north american fauna, I would strongly suggest bovines of some kind. The auroch (Bos primigenius) was easily domesticated and became cattle (Bos taurus), and although it was bred for labor & meat, thus producing thick and slow animals (slower than horses, at least), I don't see why you couldn't breed aurochs for speedy mounts (we don't know their exact running speed because they went extinct before we could record it, but multiple written accounts–including Julius Caesar's in his Commentarii de Bello Gallico–specify that they were fast and agile).
Plus they're very resilient, and could be well suited to your setting's climate. The only downside is maintenance: they need a while to eat, being ruminants.
In other parts of the world, bovines are used when horses aren't native and/or practical: zebu riding in Asia, yak riding in the Himalayan region...
2. Camelids
This might be a wild stretch, but there are camelids that live in temperate to cool (although dry) climate: llamas and alpacas could fit the bill. They are being used as mount in South America, and their running speed is nothing to be ashamed of.