Hola. No hay problema con generar la clave desde otro usuario. Lo importante es tener la clave privada asociada a la clave pública con la que les creamos el usuario nosotros (que es la que uds entregan).
El único problema es que putty usa otro formato de clave que OpenSSH. Si generás la clave en linux tenés que convertir la clave privada al formato de putty usando la aplicación puttygen. Vas al menún "Conversión" y ahí cargás la clave privada generada en linux y la guardás en el formato de putty.
De la misma forma, si generás las claves en putty, tenés que copiar y pegar la clave pública que te genera en un documento de texto y entregar eso.
Acá está bien explicado.
Saludos!