I'm not sure if there's some subtle difference in nuance or "feeling" between の and が in cases like this, but I don't think it affects the actual meaning. Whether you use の or が, I would understand it as "magic that (someone) has never seen before", where the subject of 見た is omitted but in this case is presumably meant as "you" or "people in general".
I'm only a learner, so hopefully someone will correct me if I'm wrong.