Using Template Matching on different sizes efficiently
The easiest way is to use feature matching instead of template matching. Feature matching is exactly meant for this kind of applications. It can also detect if the image is rotated .. etc
Have a lock at thishttps://docs.opencv.org/master/dc/dc3/tutorial_py_matcher.html
What you are looking for isn't that simple. The need is for multi-scale template matching, but as you mentioned, it will be slow, especially when the image resolution is pretty high.
The best and easiest solution for such cases is to train a convolutional neural network, a small one. Make use of transfer learning and train an SSD mobilenet on your data and you'll have a network that can do this detection pretty well for you and trust me it will be really fast. Object detection would give you the fastest, better, and more accurate solutions here.
Here's a link for an article explaining how to train for object detection in videos.