WireGuard is an extremely simple yet fast and modern VPN that utilizes state-of-the-art cryptography. It aims to be faster, simpler, leaner, and more useful than IPSec, while avoiding the massive headache. It intends to be considerably more performant than OpenVPN. WireGuard is designed as a general purpose VPN for running on embedded interfaces and super computers alike, fit for many different circumstances. Initially released for the Linux kernel, it plans to be cross-platform and widely deployable. It is currently under heavy development, but already it might be regarded as the most secure, easiest to use, and simplest VPN solution in the industry.
https://www.wireguard.com/

1. Install Wireguard on Ubuntu

sudo add-apt-repository ppa:wireguard/wireguard
sudo apt-get update
sudo apt-get install wireguard-dkms wireguard-tools

Generate public key and private key

(umask 077 && printf "[Interface]\nPrivateKey = " | sudo tee /etc/wireguard/wg0.conf > /dev/null)
wg genkey | sudo tee -a /etc/wireguard/wg0.conf | wg pubkey | sudo tee /etc/wireguard/publickey

Create configuration file

sudo nano /etc/wireguard/wg0.conf

[Interface]
PrivateKey = YOUR_PRIVATE_KEY
ListenPort = 5555
SaveConfig = false
Address = 10.0.0.1/24

Start Wireguard

sudo wg-quick up wg0

Type this command to show Wireguard status

sudo wg

Output

interface: wg0
  public key: SERVER_PUBLIC_KEY
  private key: (hidden)
  listening port: 5555

2. Set-up on Android

Download and install Wireguard from Google Play

https://play.google.com/store/apps/details?id=com.wireguard.android

Launch Wireguard, and create a new connection profile

• Click the + button
• "Create from scratch"
• Give a name (without using any special character)
• Click "GENERATE" beside "Private key", to generate the private-key and the public-key
• Fill in "10.0.0.2/32" for "Addresses"
• Fill in "1.1.1.1,1.0.0.1" or "8.8.8.8,8.8.4.4", etc for "DNS servers"

Add the server (peer) information

• Click "ADD PEER"
• Fill in the server-public-key
• Fill in "0.0.0.0/0" for "Allowed IPs"
• Fill in the IP or domain-name with port-number for "Endpoint"
• (e.g.123:456:789:123:5555 or mydomain.com:5555)

3. Finishing the configuration on the server

On Wireguard Android app
Click on "Public key" field on the upper "Interface" part, to copy the key
Paste the key on the server configuration file
Edit the file /etc/wireguard/wg0.conf on your server

[Interface]
PrivateKey = YOUR_PRIVATE_KEY
ListenPort = 5555
SaveConfig = false
Address = 10.0.0.1/24

[Peer]
PublicKey = PUBLIC_KEY_ON_ANDROID
AllowedIPs = 10.0.0.2/32

Save it, and restart Wireguard

sudo wg-quick down wg0
sudo wg-quick up wg0

Now you can try connecting the server on your Android phone.
If the connection is established, you can see something like this

interface: wg0
  public key: SERVER_PUBLIC_KEY
  private key: (hidden)
  listening port: 5555
peer: PHONE_PUBLIC_KEY
  endpoint: PHONE_IP:PHONE_PORT
  allowed ips: 10.0.0.2/32
  latest handshake: 3 seconds ago
  transfer: 148 B received, 92 B sent

To make Wireguard starts-up automatically, run this

sudo systemctl enable wg-quick@wg0

Re-route Internet traffic

sudo nano /etc/wireguard/wg0.conf

[Interface]
PrivateKey = YOUR_PRIVATE_KEY
ListenPort = 5555
SaveConfig = false
Address = 10.0.0.1/24
PostUp = iptables -A FORWARD -i wg0 -j ACCEPT; iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE
PostDown = iptables -D FORWARD -i wg0 -j ACCEPT; iptables -t nat -D POSTROUTING -o eth0 -j MASQUERADE

(eth0 is the network interface)

Enable packet forward

sudo nano /etc/sysctl.conf

Add these two lines if you haven't done this before

net.ipv4.ip_forward = 1
net.ipv6.conf.all.forwarding = 1

Save the file, reboot or enable it immediately with this

sudo sysctl -p