Think about it. Isn’t light+eyes and ears+sound just the same in terms of their “influence at a distance”? We don’t feel that as abnormal or magic - simply because we’ve sensors for them and are used to it. But physically speaking light and magnetism are based on electromagnetic forces.
I think it also feels like magic because we haven’t developed much intuition about the way magnets work. If you had thousands or millions of magnetic items in your life, you would develop that intuition, which would shatter the magic. Obviously, not being able to see or feel magnetic fields plays a big role too.
For example, ropes, strings and cables are very familiar. You have a good intuitive understanding on how they work, because you’ve used them so much. There’s nothing magical about them. Imagine what it would be like if today is the first day when you learn to tie a knot. You could do completely magical things like attach two ropes together. You could even keep a box closed by tiring a rope around it.
We kinda do though, we just don't often see them as having magnets but most electric motors work on principles of magnetism.
We can also see a knot and understand that is how the rope is doing what we want. We cant see magnetic fields, nor can we even detect them directly with our senses aside from metal fillings around a magnet. If we could detect magnetic fields like some fish, we would probably find magnets much more intuitive.