.
Hail esteemed neighbour (and cousin )

The title of Khan might have been in use well into the christian times. Several christian nomadic peoples used it in Eurasia. But I would also prefer Tzardom, since good old Boris had long ago styled himself thusly.

As for All Russias, that's accurate. The Tzar of of Russias (each principality being a Russia) was the title of Ivan the Terrible IIRC.


.