Well, you need to normalize and since you are working with letters, you can sort it when creating a key. So, something like this would work:
library(tidyverse)
mydf <- tibble::tribble(
~Col_A, ~Col_B,
"A", "C",
"B", "B",
"A", "C",
"A", "C",
"C", "A"
) %>%
dplyr::mutate(normalized = purrr::map2_chr(Col_A, Col_B, ~paste(sort(c(.x, .y)), collapse = ""))) %>%
dplyr::group_by(normalized) %>%
dplyr::summarise(Col_A = dplyr::first(Col_A),
Col_B = dplyr::first(Col_B)) %>%
dplyr::select(-normalized)
mydf
#> # A tibble: 2 x 2
#> Col_A Col_B
#> <chr> <chr>
#> 1 A C
#> 2 B B
Created on 2019-08-01 by the reprex package (v0.3.0)
With 300k rows it still won't be too slow, I think.