I'd say level 17/18 is a fair level to aim for, and I know it's stupid but it's worth noting just in case, are you making sure your characters aren't using melee attacks on him? He's flying so you need to use magic/ranged attacks.
Use the Eksir Berries on it too, it weakens it.
