NA seems maybe a touch too high for likely CR, but not much. The other ideas sound pretty good. As suggested before, let's add barbed defense.
CR 7?
10-13 HD (Large), 14-27 HD (Huge)?

(Dungeons & Dragons)
Rulebook featuring "high magic" options, including a host of new spells.