Best way to use replaceAll for each string in List<String>

I have a map which contains regexpr as key and replacer as value and I need to perform a replaceAll for each string in a list.

I should like to know if my answer is correct or if there exists a better way to do that, I'm afraid to see the performance drop. Cause I need to perform this operation on a lot of lists which contain lots of strings.

Map<String,String> m_replace = null; //Map which contains regexpr,replacer

private static String replace(String s) {
    for (Map.Entry<String, String> entry : m_replace.entrySet())
        s = s.replaceAll(entry.getKey(), entry.getValue());
    return s;
}

public List<String> parseList(List<String> input) {
    return input.parallelStream()
                .map(p -> p = replace(p))
                .collect(Collectors.toList());
}