I read this short story in the early 80s, probably in a collection or anthology of some sort. The hero is a very large but aging man, who wields a solid metal quarterstaff that he crushes his foes with.
At the start of the story I think he was beginning to show his age, but the mysterious beings he served renewed his immortality by commanding him to embrace a large metal sphere which very painfully rejuvenated him to a younger and stronger state. They had done this to him many times before.
My impression is that the setting was either prehistoric Earth (similar to Howard's Hyborean Age, or Clark Ashton Smith's Hyperborea) or a very far future Jack Vance Dying Earth-type place.
It seemed like this was an introductory story to a series, but I don't recall ever seeing the character again.
I've ruled out the first couple of Thieves' World books.