You're always getting the same set because the entries are first fetched, then shuffled. To achieve what you want, you could do:
{# get all your entries ids #}
{% set allIds = craft.entries().section('yourSection').ids() %}
{# Shuffle all and slice to just 15 #}
{% set shuffledIds = shuffle(allIds) | slice(0,15) %}
{# Fetch your random entries #}
{% set entries = craft.entries.id(shuffledIds).all() %}
Or
{# get all your entries ids #}
{% set allIds = craft.entries().section('yourSection').ids() %}
{# Fetch your random entries #}
{% set entries = craft.entries().id(shuffle(allIds) | slice(0,15)).all() %}
In response to your comment then you could do something like the below:
{# set a random offset #}
{% set offset = random(0, 6000)%}
{# set a random sort #}
{% set orderBy = random(['postDate', 'id', 'title']) %}
{# set a random direction #}
{% set direction = random(['ASC', 'DESC']) %}
{# get 500 ids #}
{% set allIds = craft
.entries()
.section('posts')
.offset(offset)
.orderBy(orderBy ~ ' ' ~ direction)
.limit(500)
.ids() %}
{# Fetch your random entries #}
{% set entries = craft.entries().id(shuffle(allIds) | slice(0,15)).all() %}
With this, you only fetch 500 entries with a random offset and sorting, shuffle that pool and pick 15. This might not be as random but I doubt you'd notice it.