The method described e.g. in this answer should work for you with minor adaptation. Mainly, you'll want to add some RewriteConds to keep it from applying to any URLs corresponding to images and other actual files:
# Replace all but the last underscore with dashes internally:
RewriteCond %{REQUEST_FILENAME} !-d
RewriteCond %{REQUEST_FILENAME} !-f
RewriteRule ^([^_]*)_([^_]*_.*)$ $1-$2 [N]
# Replace the last underscore and issue a HTTP permanent redirect:
RewriteCond %{REQUEST_FILENAME} !-d
RewriteCond %{REQUEST_FILENAME} !-f
RewriteRule ^([^_]*)_([^_]*)$ /$1-$2 [L,R=301]
(Add these rules before your existing rules, but after the RewriteEngine On
line. Note that you can leave out the RewriteConds if you know you don't and won't have any actual files with underscores in their names.)
You can also modify these rules to collapse consecutive hyphens:
# Collapse all but one group of multiple hyphens internally:
RewriteCond %{REQUEST_FILENAME} !-d
RewriteCond %{REQUEST_FILENAME} !-f
RewriteRule ^([^-]*(-[^-]+)*)--+([^-]+(-[^-]+)*--.*)$ $1-$3 [N]
# Collapse the last group of hyphens and issue a HTTP permanent redirect:
RewriteCond %{REQUEST_FILENAME} !-d
RewriteCond %{REQUEST_FILENAME} !-f
RewriteRule ^([^-]*(-[^-]+)*)--+([^-]+(-[^-]+)*|)$ /$1-$3 [L,R=301]
or even do both at the same time:
# Collapse all but one group of multiple hyphens and/or underscores internally:
RewriteCond %{REQUEST_FILENAME} !-d
RewriteCond %{REQUEST_FILENAME} !-f
RewriteRule ^([^-_]*(-[^-_]+)*)(--|-_|_)[-_]*([^-_]+(-[^-_]+)*(--|_).*)$ $1-$4 [N]
# Collapse the last group of hyphens and/or underscores and issue a HTTP permanent redirect:
RewriteCond %{REQUEST_FILENAME} !-d
RewriteCond %{REQUEST_FILENAME} !-f
RewriteRule ^([^-_]*(-[^-_]+)*)(--|-_|_)[-_]*([^-_]+(-[^-_]+)*|)$ /$1-$4 [L,R=301]
(Disclaimer: I have not actually tested these rules. I believe they should work, but I might have made a typo somewhere.)
None of these rules affect query strings in any way, which is probably what you want. If you do want to replace underscores and/or multiple consecutive hyphens in query strings, too, you can do it e.g. using the method described on the Apache httpd wiki here.