After seeing the information on the 6th R.V.B you posted, I did wonder if somehow Charlotte was name after Fort Charlotte, even though her baptism took place at Fort Augustus in 1811. There is one marriage before 1800 on Coll -
McKenzie John (Widower) M Feall McPhaiden Ann Grishipoll 1799 Sep-16 1 4
I think if I were to attempt to track down a John (Something) born to a John & Peggy (Something) in Tyree & Coll it would be a bold undertaking and I would never know for sure if I had the correct person.
With the images that I posted - One is for a John McKenzie born in Kilmuir Easter a (Private) and the other is the one I initially took as my John, the Serjeant, but after taking a more indepth look at the baptisms of his children - Elizabeth, Charlotte, & John and also on his marriage record in 1805, he is always listed as a Private. I have 2 other records for 2 John McKenzie's who were Chelsea Pensioners from Tyrie & Tobermory, though they are not records for the individual alone, but a group of soldiers.
The first image is of a Serjt. Peter Shaw who was born in Alvie, Inverness-shire. He was also in the 6th R.V.B. And the reason I included his record is because a Serjt Peter Shaw was a witness at the Baptism of Elizabeth McKenzie in 1808 at Ardersier.