> # time xz -z linux-3.12.6.tar

Смотря какие настройки. Во-первых, вы забыли включить параллельное сжатие для xz (xz -T) и получили совершенно бредовые цифры (в примере, где у вас отставание по скорости в 20 раз, у меня с включенной параллельностью разница в  раз). Во-вторых, вы забыли задать сопоставимые уровни сжатия.

Вот пример. Тесты проводились в /dev/shm (исключено влияние диска), core i5 2500k OC (4 ядра), динамический turbo выключен - частота одинаковая. Смотрим на real (то, что user > real показывает, что задействовано несколько ядер).

$ time pbzip2 -k linux-3.12.6.tar; du -sb linux-3.12.6.tar.bz2

real    0m9.697s
user    0m37.125s
sys    0m0.881s
91411005    linux-3.12.6.tar.bz2

$ time xz -2 -T 4 -k linux-3.12.6.tar; du -sb linux-3.12.6.tar.xz

real    0m9.849s
user    0m37.886s
sys    0m0.094s
94734180    linux-3.12.6.tar.xz

$ time xz -3 -T 4 -k linux-3.12.6.tar; du -sb linux-3.12.6.tar.xz

real    0m16.258s
user    1m2.099s
sys    0m0.107s
92558076    linux-3.12.6.tar.xz

$ time xz -4 -T 4 -k linux-3.12.6.tar; du -sb linux-3.12.6.tar.xz
real    0m24.919s
user    1m35.865s
sys    0m0.115s
87745068    linux-3.12.6.tar.xz

$ time xz -T 4 -k linux-3.12.6.tar; du -sb linux-3.12.6.tar.xz

real    0m48.961s
user    3m0.249s
sys    0m0.203s
79542264    linux-3.12.6.tar.xz

$ time xz -9 -T 4 -k linux-3.12.6.tar; du -sb linux-3.12.6.tar.xz

real    1m26.409s
user    3m48.686s
sys    0m0.960s
76392132    linux-3.12.6.tar.xz

Итого: у xz можно получить ту же скорость, что и у pbzip2. Получим на 3.6% хуже сжатие.
Работая в 2.5 раз дольше.. эээ.. то есть *НА 16 секунд дольше* мы получаем на 4% лучше сжатие. Работая на 40 секунд дольше - на 15% лучше сжатия. Работая на 76 секунд дольше - почти на 20% лучше сжатие.
Т.е. на низких уровнях сжатия они сравнимы в пределах погрешности (на другом примере xz -2 сжал бы не хуже bzip'а), но bzip2 лучше уже сжать не сможет - а у xz можно увеличивать уровень сжатия и дальше.

Время разжатия во всех случаях примерно одинаковое (порядка 4 секунд на этой машине).

В контексте новости - вы серьезно считаете, что для kernel.org жалко потратить 76 секунд ради уменьшения трафика на 20%?