Keethrax is vulnerable to acid and magic missiles.
With magic missiles, a wand will do as long as you can bounce it off a wall and hit him twice.
Wand of acid makes short work of him, or a spell if you've got it.
And yeah, he gets worse the longer you wait. I usually make my way down to L7 and if I haven't found anything to beat him by then, I will leave. He is then fixed at that difficulty level.