They do teleport, but they are supposed to do so only when the player is not around, so you should never actually see it. For example, if you run directly to the Monastery, Milten will still beat you to it, despite walking at a very slow pace. However, if you follow him, you can walk with him the whole way.