Is it possible to add a cipher for an sftp client

The Cipher directive is for SSH version 1 (which is not in use nowadays).

For SSH version 2, use the Ciphers:

sftp -oCiphers=aes256-ctr

See the ssh_config man page.

Though note that the sftp supports the -c switch too. So there's no need for using the -o.

See the sftp man page:

-c cipher

Selects the cipher to use for encrypting the data transfers.
This option is directly passed to ssh(1).

The option is supported since OpenSSH 5.4. The change is disguised as "Support most of scp(1)'s commandline arguments in sftp(1)".

Note the command-line argument -c is primarily an equivalent to the Ciphers directive (while it can fall back to the Cipher). Quote from the ssh man page:

-c cipher_spec

Selects the cipher specification for encrypting the session.
Protocol version 1 allows specification of a single cipher. The supported values are “3des”, “blowfish”, and “des”. For protocol version 2, cipher_spec is a comma-separated list of ciphers listed in order of preference. See the Ciphers keyword in ssh_config(5) for more information.

Unfortunately I can't comment yet.

What comes to my mind on the client:

Have you had a look at top to see the CPU load? Maybe the SSH process uses up CPU for encryption.

Have you had a look at ssh -v[vv] and inspected for some strangeness? Maybe server and client agree on a very secure cipher or MAC. Have a look for

debug2: ciphers ctos: arcfour
debug2: ciphers stoc: arcfour
[...]
debug1: kex: server->client cipher: arcfour MAC: hmac-sha2-256-etm@openssh.com compression: zlib@openssh.com
debug1: kex: client->server cipher: arcfour MAC: hmac-sha2-256-etm@openssh.com compression: zlib@openssh.com

(where arcfour is really one of the weakest, lowest-CPU algorithms. I am connecting via an SSH proxy). Also, look for rekeying messages.

Also, compression might be an issue. However, ssh does not seem to be too explicit about the compression level here.

debug2: compression ctos: zlib@openssh.com,zlib,none
debug2: compression stoc: zlib@openssh.com,zlib,none

You didn't say explicitly, how 'remote' your remote servers are. In the same network, in a different network on the same campus, via the internet?

If via the internet, maybe your corporate firewall is deep-inspecting SSH traffic on port 22. Maybe a port change could help, if you can control the SSH servers /etc/ssh/sshd_config file.

If via the internet, is SSH the 'only' tunnel you use, or are you using SSH via an additional VPN?

If on the same campus, also firewalling, routing, inspecting issues come to my mind. I once was blaming my internet provider for problems with my internet; it was damn slow. Went on for days. Until I found out that I enabled debugging on my Cisco router, which ate up resources there.

If local or remote, are you connecting directly or via an SSH proxy, gateway or jump host? In that case, like with the VPN, you have double encryption.