An ideal state is that you are buffed and enemy not (if not outright debuffed). Admittedly I'm getting closer and closer to level up everything in my Kingdom to lvl 23, Shrines and Keeps sure help, also I have at least Epic as governors here - which can make a big difference vs Medium Rare
Anyway, I always create a special team - cuz I need to. And Stego is one of the easier. Tried like four times and won, almost without re-rolls this time. The biggest problem was to survive his first tail swipe - so when he swiped before I could stun him and cast my buffs.
The second obstacle was his healing in the end, neverthless I finished him off.
Pegasi is probably better than Statue, because it's Yellow and Stego has just halved damage to it and Pegasi primary counter attack was merely a negligible heal.
What team you use? Pic?