If you need to change rotation potentially every frame, then a script that runs every frame is pretty much the way to go.
In the example screenshot there are maybe 30 sprites on screen. It would be very difficult to cause a noticeable performance impact from doing anything a mere 30 times per frame. So as TomTsagk says in a comment, you should definitely test out this simplest, most direct option first, and profile it to verify whether there's any real problem that might force you to do something more complex.
If your camera only rotates in discrete hops, you could set up this script to run only when the camera moves (so, in the same script where you listen for the Q/E key press to start the camera move, you also fire off the billboarding update). Then at least it's not running redundantly when the camera angle stays fixed.
You want to orient the sprites or quads to face along (the negation of) the camera's forward vector. That means you don't need to change the sprite rotation when the camera translates, only when it rotates.
Technically, you could also accomplish this by abuse of a particle system, which have built-in billboarding options. Those compute new billboarded quads for every particle every frame without significant performance impact, even for thousands of simultaneous particles on screen. But the indirection of routing all your sprite positioning and animation updates through a particle buffer is likely to get onerous and sap more productivity than it is worth.
Lastly, you could implement the billboarding effect in a shader, repositioning the vertices to snap them to face the camera just before rasterizing the sprite. This is a little complicated to do without breaking sprite batching though, as the vertices would somehow need to figure out where the sprite's pivot is, to rotate the billboard around that. Normally that info has already been baked down by that stage of the pipeline, so it would be extra work to reconstruct.
So, I'd say: try the simple rotation script first. Profile it. If you find it has an unacceptable cost, update your question with your findings and we can explore potential fixes. But those fixes are themselves complicated enough to be a net drain on your productivity if they're not truly needed.
Have a script that at all times perfectly rotate the object to directly face the camera. This seems very inefficient.
Usually billboarding is done in a similar way, where the camera's rotation is also applied to a sprite, this ensures that the sprite will pretty much look at the camera. Have you noticed any performance issues to suggest this is inefficient? \$\endgroup\$