対象の文字列がすごく長いときや、変換元の文字列が1文字でない場合には
puts str.gsub(Regexp.union(*repl.keys), repl)
こんな感じ？