Help to optimize an index in mysql

Question

I own a site of relationships and for years I try to optimize this query. Almost every day the site hangs because of it.

Structure of the user table

CREATE TABLE `usuarios` (
  `id` bigint(20) NOT NULL,
  `nome` varchar(25) CHARACTER SET utf8 COLLATE utf8_unicode_ci DEFAULT NULL,
  `cidade` varchar(50) CHARACTER SET utf8 COLLATE utf8_unicode_ci DEFAULT NULL,
  `latitude` float(6,2) NOT NULL DEFAULT '0.00',
  `longitude` float(6,2) NOT NULL DEFAULT '0.00',
  `ano_nascimento` smallint(4) NOT NULL DEFAULT '1997',
  `genero` tinyint(1) NOT NULL DEFAULT '1',
  `genero_procuro` tinyint(1) NOT NULL DEFAULT '2',
  `idade_minima` tinyint(2) NOT NULL DEFAULT '18',
  `idade_maxima` tinyint(2) NOT NULL DEFAULT '80',
  `unix_timestamp_online` int(10) NOT NULL DEFAULT '0',
  `usuario_bloqueado` tinyint(1) NOT NULL DEFAULT '1',
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

Indexes

ALTER TABLE `usuarios`
ADD PRIMARY KEY (`id`),
ADD KEY `indice_composto`(
    `unix_timestamp_online`,
    `usuario_bloqueado`,
    `genero`,
    `genero_procuro`,
    `idade_maxima`,
    `idade_minima`,
    `ano_nascimento`,
    `latitude`,
    `longitude`
) USING BTREE;

Example of consultation

SELECT id, latitude, longitude 
FROM usuarios 
WHERE genero=2 
AND id NOT IN (11111111,2222222) 
AND (ano_nascimento BETWEEN 1961 AND 1999) 
AND (latitude BETWEEN -25.14 AND -16.13) 
AND (longitude BETWEEN -54.87 AND -45.86) 
AND usuario_bloqueado=0 
AND idade_minima<=35 
AND idade_maxima>=35 
AND genero_procuro IN(0,1) 
ORDER BY unix_timestamp_online DESC 
LIMIT 20

Summarizing the conditions of the example query..

• I am masculino=1 and I’m looking for users of the genre feminino=2
• I exclude some ids
• Were born among 1961 AND 1999
• Are in latitude, longitude...
• They have no type of bloqueio=0
• My idade=35 needs to be acceptable by these users
• My gender also needs to be acceptable (todos=0, male=1)
• I order displaying users who are online first

I believe that the composite index that was created is not so beautiful, but in every way I tried, it was the one that brought the least slow consultations. You have an appointment that takes less than 1 second, another one takes 4, another 10, 20 and so on. It’s hard to report what I’ve tried, because it was almost all combinations of indexes...
I may be missing just one detail, in the index, in select, maybe I need to look for another bank, I don’t know, any help is welcome. Thank you.

EDITED:

Explain of example query

id: 1
select_type: SIMPLE
table: usuarios
partitions: NULL
type: index
possible_keys: PRIMARY
key: indice_composto
key_len: 19
ref: NULL
rows: 20
filtered: 0.25
Extra: Using where; Using index

This query takes on average 0.0020 seconds

If I change the ano_birth condition to (ano_nascimento BETWEEN 1999 AND 1999)

The explain is identical and the query takes on average 9.1376 seconds