As the order doesn't matter, you can look at all the sorted words instead. You can also prebuild an index and make sure the code is warmer. Looking at a dictionary of 22K words, it takes an average of 9 micro-seconds on my laptop

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class WordsSearchMain {
    public static void main(String... ignored) throws IOException {
        Dictionary dict = new Dictionary("/usr/share/dict/words", 3, 6);
        final String alphabet = "abcdefghifjklmnopqrstuvwxyz";
        String[] words = new String[22];
        for (int i = 0; i < words.length; i++)
            words[i] = alphabet.substring(i, i + 6);

        // warmup the code
        for (int i = 0; i < 12000; i += words.length)
            for (String word : words)
                dict.allWordsFor(word);
        // time to do 20 searches
        Map<String, Set<String>> searches = new LinkedHashMap<>();
        long start = System.nanoTime();
        for (String word : words)
            searches.put(word, dict.allWordsFor(word));
        long time = System.nanoTime() - start;

        System.out.printf("Took an average of %.1f micro-seconds, searching %,d words%n",
                time / words.length / 1e3, dict.count);
        for (Map.Entry<String, Set<String>> entry : searches.entrySet()) {
            System.out.println(entry);
        }
    }

}

class Dictionary {
    private final int min;
    Map<String, List<String>> wordForLetters = new HashMap<>();
    int count = 0;

    public Dictionary(String filename, int min, int max) throws IOException {
        this.min = min;
        try (BufferedReader br = new BufferedReader(new FileReader(filename))) {
            for (String line; (line = br.readLine()) != null; ) {
                if (line.length() >= min && line.length() <= max) {
                    char[] chars = line.toLowerCase().toCharArray();
                    Arrays.sort(chars);
                    String sorted = new String(chars);
                    List<String> words = wordForLetters.get(sorted);
                    if (words == null)
                        wordForLetters.put(sorted, words = new ArrayList<>());
                    words.add(line);
                    count++;
                }
            }
        }
    }

    public Set<String> allWordsFor(String s) {
        Set<String> allWords = new TreeSet<>();
        String lower = s.toLowerCase();
        for (int i = (1 << min) - 1; i < (1 << s.length()); i++) {
            int bitCount = Integer.bitCount(i);
            if (bitCount < min) continue;
            StringBuilder sb = new StringBuilder(bitCount);
            for (int j = 0; j < s.length(); j++)
                if (((i >> j) & 1) != 0)
                    sb.append(lower.charAt(j));
            final List<String> words = wordForLetters.get(sb.toString());
            if (words != null)
                allWords.addAll(words);
        }
        return allWords;
    }
}

Prints

Took an average of 9.1 micro-seconds, searching 22,299 words
abcdef=[Abe, Dec, Feb, Fed, abed, ace, aced, bad, bade, bead, bed, cab, cad, dab, deaf, deb, decaf, face, faced, fad, fade, fed]
bcdefg=[Dec, Feb, Fed, bed, beg, deb, fed]
cdefgh=[Che, Dec, Fed, chef, fed]
defghi=[Fed, Gide, die, dig, fed, fie, fig, hid, hide, hie, hied]
efghif=[fie, fig, hie]
fghifj=[fig, jig]
ghifjk=[JFK, jig]
hifjkl=[JFK, ilk]
ifjklm=[JFK, Jim, Kim, ilk, mil, milk]
fjklmn=[JFK]
jklmno=[Jon, Lon, Mon, Monk, monk]
klmnop=[Lon, Mon, Monk, Polk, lop, monk, mop, pol]
lmnopq=[Lon, Mon, Qom, lop, mop, pol]
mnopqr=[Mon, Qom, Ron, mop, morn, nor, norm, porn, pro, prom, romp]
nopqrs=[Ron, Son, nor, porn, pro, pros, son, sop]
opqrst=[Post, opt, opts, port, ports, post, pot, pots, pro, pros, rot, rots, sop, sort, sot, sport, spot, stop, strop, top, tops, tor, tors]
pqrstu=[Prut, Stu, pus, put, puts, rust, rut, ruts, spur, spurt, sup, ups]
qrstuv=[Stu, rust, rut, ruts]
rstuvw=[Stu, rust, rut, ruts]
stuvwx=[Stu, tux]
tuvwxy=[tux]
uvwxyz=[]