Warrior-Maid of Mars by Alfred Coppel

For what seemed a long time, Telis floated in throbbing darkness. Pain spun in little wind-devils of fire across the surface of his mind and it was not physical pain alone. Two thoughts tortured him constantly. He had failed the Maldia and he had deserted his friend, leaving him to die at the hands of the cannibal tribesmen.

Aeons swept by in that timeless, vitalizing darkness, and at last Telis opened his eyes.